Sort List

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

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode merge(ListNode node1, ListNode node2) {
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    while (node1 != null && node2 != null) {
        if (node1.val < node2.val) {
            runner.next = node1;
            node1 = node1.next;
        } else {
            runner.next = node2;
            node2 = node2.next;
        }
        runner = runner.next;
    }
    if (node1 != null) {
        runner.next = node1;
    } else {
        runner.next = node2;
    }
    return dummyHead.next;
}


public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) { // check head.next is important
        return head;
    }
    ListNode mid = findMiddle(head);
    ListNode midPost = mid.next;
    mid.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(midPost);

    return merge(left, right);
}

Share