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; }

// 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; }