python 排序链表

[python]代码库

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeSort(head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head

    # Find the middle of the linked list
    slow = head
    fast = head.next

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    # Recursively split the linked list into two halves
    left = mergeSort(head)
    right = mergeSort(mid)

    # Merge the sorted halves
    dummy = ListNode(0)
    curr = dummy

    while left and right:
        if left.val < right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next

        curr = curr.next

    curr.next = left or right

    return dummy.next

# Test the program
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

sorted_list = mergeSort(head)

# Print the sorted linked list
curr = sorted_list
while curr:
    print(curr.val)
    curr = curr.next