# Sort List

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)

/**
* 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);
}
}