Reference: LeetCode Difficulty: Medium Slow/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 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; } List<ListNode> array = new ArrayList <>(); ListNode p = head; while (p != null ) { array.add(p); p = p.next; } Comparator<ListNode> comp = (ListNode o1, ListNode o2) -> (o1.val - o2.val); array.sort(comp); 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); ListNode left = mergesort(splitResult[0 ]); ListNode right = mergesort(splitResult[1 ]); return mergeList(left, right); } 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 }; } 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 ) { ListNode p = dummy.next; ListNode prev = dummy; while (p != null ) { ListNode[] result = split(p, n); ListNode left = result[0 ]; ListNode rest = result[1 ]; result = split(rest, n); ListNode right = result[0 ]; rest = result[1 ]; result = mergeList(left, right); prev.next = result[0 ]; 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 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; } ListNode rest = p.next; p.next = null ; return new ListNode [] { head, rest }; } private ListNode[] mergeList(ListNode n1, ListNode n2) { 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; while (prev.next != null ) prev = prev.next; return new ListNode [] { dummy.next, prev }; } 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 private ListNode findMid (ListNode x) { if (x == null || x.next == null ) { return x; } ListNode slow = x; ListNode fast = x; while (fast.next != null && fast.next.next != null ) { slow = slow.next; fast = fast.next.next; } return slow; } ```java private ListNode findMid (ListNode x) { if (x == null || x.next == null ) { return x; } ListNode slow = x; ListNode fast = x; while (fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; } return slow; }