public class Solution {
public ListNode sortList(ListNode head) {
if (head == null  head.next == null)
return head;
// step 1. cut the list to two halves
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
// step 2. sort each half
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// step 3. merge l1 and l2
return merge(l1, l2);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
}
Java merge sort solution



@wei88
You are indeed right, the space complexity is O(logn), because the sortList function is called recursively. Also, a new node is created for each time a merge function is called. Since both merge and sortList are called logn times, the space is O(logn).

I dont quite understand why we need to define a "pre" node pointing to the node before slow. You use the PRE node to cut the linked list but what if I want to use the SLOW node? Suppose we have a linked list "5>4>1>3>2", when we finish the preslowfast movement once, the result linked list should be "5>4" and "1>3>2" while we have "5>4>1" and "3>2" for using slowfast movement. What's the difference between these two?

@cqy0118
prev
points to theListNode
beforeslow
. If we doslow.next = null
then when there are only two elements left, it will be a infinite loop, sinceslow
will always point to the second node andsort(head)
will fail to divide the last two nodes and always result in the last two nodes, hence the stack overflow error.
