Sort a linked list in O(n log n) time using constant space complexity.
Solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode dummy=new ListNode(0), fast=dummy, slow=dummy;
dummy.next=head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode l2 = sortList(slow.next);
slow.next = null;
ListNode l1 = sortList(dummy.next);
return merge(l1, l2);
}
public ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0), pre = dummy;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
if(l1!=null) pre.next = l1;
else pre.next = l2;
return dummy.next;
}
}