Reference: LeetCode
Difficulty: MediumSlow/Fast Pointers

My Post: Java Mergesort for Sort List (Recursion & Iteration)

Problem

Sort a linked list in $O(N\log{N})$ time using constant space complexity.

Example:

1
2
3
4
5
Input: 4->2->1->3
Output: 1->2->3->4

Input: 4->2->1->3->5
Output: 1->2->3->4->5

Analysis

Naive (Extra Space)

Note: Be careful of linked list generation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode naiveSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// toArray
List<ListNode> array = new ArrayList<>();
ListNode p = head;
while (p != null) {
array.add(p);
p = p.next;
}
// sort
Comparator<ListNode> comp = (ListNode o1, ListNode o2) -> (o1.val - o2.val);
array.sort(comp);
// generate linked list
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
for (int i = 0; i < array.size(); ++i) {
prev.next = array.get(i);
prev = prev.next;
}
prev.next = null;
return dummy.next;
}

Time: $O(N + N\log{N} + N) = O(N\log{N})$
Space: $O(N)$

Mergesort + Slow/Fast Pointers

Recursion

Note:

  • It seems bad to use right-leaning splitInHalf, because you can’t split the list (set the previous node of mid to null).
  • Since we need to set mid.next to null, we can do right mergeSort first. Clean code.
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
public ListNode sortList(ListNode head) {
return mergesort(head);
}

private ListNode mergesort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode[] splitResult = splitInHalf(head); // O(N)
ListNode left = mergesort(splitResult[0]);
ListNode right = mergesort(splitResult[1]);
return mergeList(left, right); // O(N)
}

private ListNode mergeList(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;

while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
prev.next = head1;
head1 = head1.next;
} else {
prev.next = head2;
head2 = head2.next;
}
prev = prev.next;
}

if (head1 != null) prev.next = head1;
if (head2 != null) prev.next = head2;

return dummy.next;
}


private ListNode[] splitInHalf(ListNode head) {
if (head == null) {
return new ListNode[] { null, null };
}
// left-leaning
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode[] result = new ListNode[] { head, slow.next };
slow.next = null;
return result;
}

Time: $O(N\log{N})$
Space: $O(\log{N})$

Iteration

Each time we double n.

  • split(head, n) that splits input head into [n nodes, the rest].
    • We need to handle a case that n is larger than the number of available nodes.
  • mergeList(n1, n2) returns [head, tail] of the merged list.

Note: In each loop, p should be initialized with dummy.next rather than head, since head might be changing.

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
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int len = getLength(head);
ListNode dummy = new ListNode(-1);
dummy.next = head;

for (int n = 1; n < len; n *= 2) { // splitting unit
ListNode p = dummy.next; // head may be changed!!!
ListNode prev = dummy;
while (p != null) {
// split
ListNode[] result = split(p, n);
ListNode left = result[0];
ListNode rest = result[1];
result = split(rest, n);
ListNode right = result[0];
rest = result[1]; // might be null
// merge
result = mergeList(left, right);
prev.next = result[0];
// update
prev = result[1];
p = rest;
}
}
return dummy.next;
}

Helper functions:

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
// Splits into [n nodes, rest part]
private ListNode[] split(ListNode head, int n) {
if (head == null || head.next == null) {
return new ListNode[] { head, null };
}
ListNode p = head;
while (n > 1 && p.next != null) {
p = p.next;
--n;
} // p stops at the n-th node (so it should be n > 1)
ListNode rest = p.next;
p.next = null;
return new ListNode[] { head, rest };
}

// Returns [first node, last node] after merging
private ListNode[] mergeList(ListNode n1, ListNode n2) { // n1, n2 are sorted
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (n1 != null && n2 != null) {
if (n1.val < n2.val) {
prev.next = n1;
n1 = n1.next;
} else {
prev.next = n2;
n2 = n2.next;
}
prev = prev.next;
}
prev.next = (n1 != null) ? n1 : n2;

// reach the tail
while (prev.next != null) prev = prev.next;
return new ListNode[] { dummy.next, prev };
}

// Get Length
private int getLength(ListNode x) { ... }

Tips for Slow/Fast Pointers

Note: Use two pointers to find the middle node in the list. But there are two cases: left-leaning and right-leaning.

The difference lies in the while condition.

  • Left-leaning: while (fast.next != null && fast.next.next != null) You can see this as a stricter constraint
  • Right-leaning: while (fast != null && fast.next != null)
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
// Left-leaning
// 1 2 3 4 5
// s s s
// f f f
// ----------
// 1 2 3 4
// s s
// f f
private ListNode findMid(ListNode x) {
if (x == null || x.next == null) {
return x;
}
ListNode slow = x; // left-leaning
ListNode fast = x;
while (fast.next != null && fast.next.next != null) { // here is the different
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

```java
// Right-leaning
// ----------
// 1 2 3 4 5
// s s s
// f f f
// ----------
// 1 2 3 4
// s s s
// f f f
private ListNode findMid(ListNode x) {
if (x == null || x.next == null) {
return x;
}
ListNode slow = x; // right-leaning
ListNode fast = x;

while (fast != null && fast.next != null) { // here is the different
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

Comment