/ Data Structure and Algorithms  

Leetcode 148. Sort List

Question



Sort a linked list. Required time complexity is O(nlogn). The most commonly used method is merge sort.

Similar Questions

Solution

Firstly, merge sort requires a helper method, which is used to merge two sorted linked lists.

Merge sorting is done half and half, so we need to find the midpoint. The most common method is to find the midpoint with fast and slow pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// add a dummy pointer to the start
// so that in the end, the slow pointer always point to the last element of left half
ListNode dummy = new ListNode(0);
dummy.next = node;

// use fast and slow pointer
ListNode slow = dummy;
ListNode fast = dummy;

// split the list
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

In the above code, there is a dummy node. When the number of nodes is even, then slow just point to the last node of the previous half of the node, which is the state below.

1
2
3
1    2    3    4
     ^         ^
    slow      fast

If both slow and fast start from the head, then when fast ends, slow will go to the beginning of the next half of the node.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
public static ListNode sortList(ListNode head) {
    return mergeSort(head);
}

// helper method to split original list into 2 half
// recursive the left and right half
// merge the left and right half
private static ListNode mergeSort(ListNode node) {
    // reach the end
    if (node == null || node.next == null) {
        return node;
    }

    // add a dummy pointer to the start
    // so that in the end, the slow pointer always point to the last element of left half
    ListNode dummy = new ListNode(0);
    dummy.next = node;

    // use fast and slow pointer
    ListNode slow = dummy;
    ListNode fast = dummy;

    // split the list
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // slow is the last node of left half
    ListNode rightHalf = slow.next;

    // make slow.next = null so we have 2 split list
    slow.next = null;

    // recursive sort the left and right half
    ListNode head1 = mergeSort(node);
    ListNode right = mergeSort(rightHalf);

    return merge(head1, right);
}

// helper method to merge 2 sorted list
private static ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummyHead = new ListNode(0);
    ListNode lastNode = dummyHead;

    while (head1 != null && head2 != null) {
        if (head1.val < head2.val) {
            // head1 is smaller
            // add head1 to the last
            // move head1 to next
            lastNode.next = head1;
            lastNode = lastNode.next;
            head1 = head1.next;
        } else {
            lastNode.next = head2;
            lastNode = lastNode.next;
            head2 = head2.next;
        }
    }

    // we exit the while loop because one of the head1 or head2 reach end
    // append the other one to the last
    if (head1 != null) {
        lastNode.next = head1;
    }

    if (head2 != null) {
        lastNode.next = head2;
    }

    return dummyHead.next;
}

Of course, strictly speaking, the space complexity of the solution above is not O(1), because pushing the stack in the recursive process consumes space, and takes half each time, so the space complexity is O(logn).