# Java merge sort solution

• ``````public class Solution {

// step 1. cut the list to two halves

while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

prev.next = null;

// step 2. sort each half
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;
}

}``````

• I don't understand why it is constant space complexity? You call merge function log(length) times right? Each time you make a new ListNode l which next property is the returned list. By the way can I do it on l1 without a new listnode?

• The split part is clear and easy to understand, but the merge part uses O(n) space,

• The merge creates 1 ListNode that is all, the space complexity is not O(n), but O(1)

• Since this is a recursion method, the space complexity is O(log(n)) not O(1). I doubt this method pass OJ.

• I think leetcode's OJ system doesn't check space usage, unless you make a stackoverflow exception

• I agree with you, the space complexity is O(1). Because all the original nodes was already created in the memory (Heap), only one new ListNode created.

• This post is deleted!

• @otnt I agree with you,the number of new nodes is related to nums of merge-invoking

• The space complexity in merge function here is O(1), for the new node created. And it is not O(n) because, we are just re-assigning the pointers to already present nodes. Beautiful Solution.

• @SanD @xshen93
You forgot the space usage by stack in recursion.

// step 2. sort each half
ListNode l2 = sortList(slow);

• @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 pre-slow-fast 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 slow-fast movement. What's the difference between these two?

• This post is deleted!

• @传说选手 You need to consider list with two nodes. eg 1->2. If you are not using pre, you can't get two list 1 -> null, 2 -> null.

• have some trouble understanding why it has to be

'''
prev.next = null;

'''
I understand it is used to disconnect the linkedlist, but why can't I use slow.next=null here?(The compiler says stackoverflow exception)

• @cqy0118 `prev` points to the `ListNode` before `slow`. If we do `slow.next = null` then when there are only two elements left, it will be a infinite loop, since `slow` will always point to the second node and `sort(head)` will fail to divide the last two nodes and always result in the last two nodes, hence the stack overflow error.

• Nice explanation with comments inside code!

• This post is deleted!

• @ZhassanB It still uses extra space for the recursive calls though.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.