Sort a linked list in O(n log n) time using constant space complexity.
Example :
Input : 1 -> 5 -> 4 -> 3
Returned list : 1 -> 3 -> 4 -> 5
Method:
Use merge sort
Solution:
Time: O(nlogn) Space: O(1) or O(logn)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { private ListNode mergeSorted(ListNode A, ListNode B) { if (A == null) return B; if (B == null) return A; ListNode dummy = new ListNode(0); ListNode p = dummy; while (A != null && B != null) { if (A.val <= B.val) { p.next = A; A = A.next; } else { p.next = B; B = B.next; } p = p.next; } if (A != null) p.next = A; if (B != null) p.next = B; return dummy.next; }
private ListNode findMid(ListNode A) { if (A == null || A.next == null) return A; ListNode slow = A; ListNode fast = A.next.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; return mid; }
public ListNode sortList(ListNode A) { if (A == null || A.next == null) return A; ListNode mid = findMid(A); ListNode sortedFirst = sortList(A); ListNode sortedSecond = sortList(mid); return mergeSorted(sortedFirst, sortedSecond); } }