Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

public class Solution {
    public static ListNode findMiddle(ListNode h) {
        if (h == null)
            return h;
        ListNode slow = h;
        ListNode fast = h;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static ListNode sortedMerge(ListNode a, ListNode b) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (a != null & b != null) {
            if (a.val <= b.val) {
                temp.next = a;
                a = a.next;
            } else {
                temp.next = b;
                b = b.next;
            }
            temp = temp.next;
        }
        if (a != null)
            temp.next = a;
        if (b != null)
            temp.next = b;

        return result.next;
    }

    public ListNode sortList(ListNode A) {
        if (A == null || A.next == null)
            return A;
        ListNode Middle = findMiddle(A);
        ListNode NextMiddle = Middle.next;
        Middle.next = null;
        return sortedMerge(sortList(A), sortList(NextMiddle));

    }
}