# I have a pretty good MergeSort method. Can anyone speed up the run time or reduce the memory usage?

• ``````/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while (f != null && f.next != null) {
p = p.next;
f =  f.next.next;
}
ListNode h2 = sortList(p.next);
p.next = null;
}
public ListNode merge(ListNode h1, ListNode h2) {
ListNode hn = new ListNode(Integer.MIN_VALUE);
ListNode c = hn;
while (h1 != null && h2 != null) {
if (h1.val < h2.val) {
c.next = h1;
h1 = h1.next;
}
else {
c.next = h2;
h2 = h2.next;
}
c = c.next;
}
if (h1 != null)
c.next = h1;
if (h2 != null)
c.next = h2;
return hn.next;
}
}``````

• This post is deleted!

• The algorithm includes recursion which consumes the stack memory, it seems that the stack memory usage is not constant. I can use the bottom-up merge sort to reduce memory.

• u r so creative.

• good solution, easy to understand

• Nice solution.

I guess after the loop you can use this to make it even shorter

``````c.next = (h1 !=null) ? h1 : h2;
``````

Here is my AC solution written in javascript

``````var sortList = function(head) {
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}

slow.next = null;
};

var mergeList = function(h1, h2) {
var dummy = new ListNode(null);
var tail = dummy;
while (h1 && h2) {
if (h1.val <= h2.val) {
tail = tail.next = h1;
h1 = h1.next;
} else {
tail = tail.next = h2;
h2 = h2.next;
}
}
tail.next = h1 ? h1 : h2;
return dummy.next;
};``````

• ``````ListNode f = head.next.next;
``````

Why is it that I get a stackoverflow when I initialize both f and p to head?

• This post is deleted!

• Space complexity of the solution is not O(1), but O(nlogn). However, it's very beautiful.

• need to delete hn to avoid memory leak

• @kevinhsu same problem here, don't know the difference between

``````ListNode f = head.next.next;
``````

and

``````ListNode f = head;
``````

Pls let me know you figured it out.

• I would say it's probably the case where you have only 2 inputs, say 2->1-> null;
After the while loop, you end up getting p points to 1. Then you sort p.next (null), which won't do anything. After that you sort 2->1->null again. Stack overflow

• I suggest that by mentioning "Constant space" complexity, we should not use Recursion, which uses stack for each recursively called function.

Thus you can simply use Iteration for merge sort.

• I think space complexity is O(logn), rather than O(nlogn)

• I guess the only way to reduce space cost is to avoid to use recursion. All recursive algorithms can be implemented iteratively. But iterative code could be so complex :(

``````        if (head == null || head.next == null)
while (f != null && f.next != null) {
p = p.next;
f =  f.next.next;
}
ListNode h2 = sortList(p.next);
p.next = null;
``````

if the linkList have two element {1,2}

then p.next already is null then h2 is null

sortList(head) still have two . the recursive will not ended.

here is my code:

``````        if(!head || !head->next)

while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
slow->next = NULL;//把两条链表割断
ListNode* p1;
ListNode* p2;
{
p2 = sortList(slow);
}
else
{
}

return MergeList(p1,p2);
``````

• Well, you didn't notice he initialize ListNode f = head.next.next; rather than just head. This well solve the problem of two elements.

• rewrite CPP version

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(h2 && h2->next)
{
h1 = h1->next;
h2 = h2->next->next;
}
h2 = h1->next;
h1->next = NULL;
}
ListNode *merge(ListNode*h1,ListNode*h2)
{
while(h1 && h2)
{
if(h1->val<h2->val)
{
node->next = h1;
node = node->next;
h1 = h1->next;
}
else
{
node->next = h2;
node = node->next;
h2 = h2->next;
}
}
if(h1)  node->next = h1;
else    node->next= h2;
}
};
``````

• @potpie O(nlgn) remind me of D&C. exactly same idea.

• Following are my non-recursive solution in Java, and it won't use log(n) space complexity. Although I write the iterative solution, I still think it's better to implement it in a recursive way. It's more readable and clear.

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
int len = 0;
while (iter != null) {
len++;
iter = iter.next;
}
// step represent how long the two merging list is
for (int step = 1; step < len; step *= 2) {
for (int i = 0; i < step && p2 != null; i++) {
p2 = p2.next;
}
while (p2 != null) {
iter = merge(iter, p1, p2, step);
p1 = iter.next;
p2 = iter.next;
for (int i = 0; i < step && p2 != null; i++) {
p2 = p2.next;
}
}
}
}
// merge two listnode with max length len after head
private ListNode merge(ListNode head, ListNode node1, ListNode node2, int len) {
int count1 = 0;
int count2 = 0;
while (count1 < len || count2 < len) {
if (count1 < len && (count2 >= len || node2 == null || node1.val <= node2.val)) {
node1 = node1.next;
count1++;
} else {
if (node2 == null) break;