Ziyuan Qin's blog

Sort List

Linked ListSort
https://leetcode.com/problems/sort-list

# Definition for Singly-Linked List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
1
2
3
4

# Solution

# Merge Sort

# Recursive Top Down

complexity

time: O(nlog⁡n)O(n \log n)
space: O(log⁡n)O(\log n)

def sortList(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    fast, slow = head.next, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    # disconnect
    right_head = slow.next
    slow.next = None
    left, right = self.sortList(head), self.sortList(right_head)
    return self.merge(left, right)

def merge(self, left, right):
    if not left or not right:
        return left or right
    dummy = curr = ListNode(0)
    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Iterative Bottom Up

Gradually increase sub_len to merge iteratively.

def sortList(self, head: ListNode) -> ListNode:

    def merge(head1: ListNode, head2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy

        while head1 and head2:
            if head1.val <= head2.val:
                curr.next = head1
                head1 = head1.next
            else:
                curr.next = head2
                head2 = head2.next
            curr = curr.next
        curr.next = head1 if head1 else head2
        return dummy.next

    if not head:
        return head

    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    dummy = ListNode(0, head)
    sub_len = 1
    while sub_len < length:
        prev, curr = dummy, dummy.next
        while curr:
            head1 = curr
            for i in range(1, sub_len):
                if curr and curr.next:
                    curr = curr.next
                else:
                    break
            head2 = curr.next
            curr.next = None
            curr = head2
            for i in range(1, sub_len):
                if curr and curr.next:
                    curr = curr.next
                else:
                    break

            succ = None
            if curr:
                # split
                succ = curr.next
                curr.next = None

            merged = merge(head1, head2)
            prev.next = merged
            while prev.next:
                prev = prev.next
            curr = succ
        sub_len <<= 1

    return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

Sparse Matrix Multiplication