Sort a linked list in O(n log n) time using constant space complexity.
public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode slow = head ; ListNode fast = head.next; //like the problem find circle in list, faster and slower points to sepearte lists into two parts while(fast!=null && fast.next!=null){ slow = slow.next; fast = fast.next.next; } ListNode newHead = slow.next;//head of second half slow.next = null; head = sortList(head); newHead = sortList(newHead); return mergeList(head,newHead); } public ListNode mergeList(ListNode p1, ListNode p2){ if(p1 == null) return p2; if(p2 == null) return p1; ListNode p = new ListNode(0); ListNode head = p; while(p1 != null || p2!=null){ if ((p1 != null && p2 != null && p1.val < p2.val) || p2 == null){ head.next = p1; p1 = p1.next; } else{ head.next = p2; p2 = p2.next; } head = head.next; } return p.next; } }