/**
* Definition for singlylinked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null  head.next == null)
return head;
ListNode f = head.next.next;
ListNode p = head;
while (f != null && f.next != null) {
p = p.next;
f = f.next.next;
}
ListNode h2 = sortList(p.next);
p.next = null;
return merge(sortList(head), h2);
}
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;
}
}
I have a pretty good MergeSort method. Can anyone speed up the run time or reduce the memory usage?


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) { if (!head  !head.next) return head; var fast = head.next.next; var slow = head; while (fast && fast.next) { fast = fast.next.next; slow = slow.next; } var head1 = sortList(slow.next); slow.next = null; var head2 = sortList(head); return mergeList(head1, head2); }; 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; };

@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.

In your code
if (head == null  head.next == null) return head; ListNode f = head.next.next; ListNode p = head; while (f != null && f.next != null) { p = p.next; f = f.next.next; } ListNode h2 = sortList(p.next); p.next = null; return merge(sortList(head), h2);
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) return head; ListNode* slow = head; ListNode* fast = head; while(fast && fast>next) { slow = slow>next; fast = fast>next>next; } ListNode* head2 = slow>next; slow>next = NULL;//把两条链表割断 ListNode* p1; ListNode* p2; if(!head2) //注意两个元素的 情况 { head>next = NULL; p1 = sortList(head); p2 = sortList(slow); } else { p1 = sortList(head); p2 = sortList(head2); } return MergeList(p1,p2);

rewrite CPP version
/** * Definition for singlylinked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head) { if(head==NULL  head>next==NULL) return head; ListNode *h1 = head; ListNode*h2 = head>next>next; while(h2 && h2>next) { h1 = h1>next; h2 = h2>next>next; } h2 = h1>next; h1>next = NULL; return merge(sortList(head),sortList(h2)); } ListNode *merge(ListNode*h1,ListNode*h2) { ListNode *newHead = new ListNode(INT_MIN); ListNode *node =newHead ; 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; return newHead>next; } };


Following are my nonrecursive 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.
/** * Definition for singlylinked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { int len = 0; ListNode iter = head; while (iter != null) { len++; iter = iter.next; } ListNode fakeHead = null; // step represent how long the two merging list is for (int step = 1; step < len; step *= 2) { fakeHead = new ListNode(0); iter = fakeHead; fakeHead.next = head; ListNode p1 = head; ListNode p2 = head; 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; } } head = fakeHead.next; } return head; } // 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)) { head.next = node1; node1 = node1.next; count1++; } else { if (node2 == null) break; head.next = node2; node2 = node2.next; count2++; } head = head.next; } head.next = node2; return head; } }