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

Have you met this question in a real interview?

Yes

Example

Given1->3->2->null, sort it to1->2->3->null.

1. merge sort

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head) {  
        // write your code here
        if (head == null) {
            return head;
        }
        return mergeSortHelper(head);
    }

    //find middle and divide into left and right
    public ListNode mergeSortHelper(ListNode head) {
        //exit
        if (head.next == null) {
            return head;
        }

        ListNode middle = findMiddle(head);
        ListNode rightHead = middle.next;
        middle.next = null;

        ListNode left = mergeSortHelper(head);
        ListNode right = mergeSortHelper(rightHead);

        return merge(left, right);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }

            head = head.next;
        }

        while (l1 != null) {
            head.next = l1;
            l1 = l1.next;
            head = head.next;
        }

        while (l2 != null) {
            head.next = l2;
            l2 = l2.next;
            head = head.next;
        }

        return dummy.next;
    }

    //1->2->3->4->5
    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
}

1. quick sort

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head) {  
        // write your code here
        if (head == null) {
            return head;
        }

        ListNode leftDummy = new ListNode(0);
        ListNode middleDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);

        ListNode leftHead = leftDummy;
        ListNode rightHead = rightDummy;
        ListNode middleHead = middleDummy;

        ListNode mid = findMiddle(head);

        while (head != null) {
            if (head.val < mid.val) {
                leftDummy.next = head;
                leftDummy = head;
            } else if (head.val > mid.val) {
                rightDummy.next = head;
                rightDummy = head;
            } else {
                middleDummy.next = head;
                middleDummy = head;
            }

            head = head.next;
        }

        leftDummy.next = null;
        rightDummy.next = null;
        middleDummy.next = null;

        ListNode left = sortList(leftHead.next);
        ListNode right = sortList(rightHead.next);

        return concat(left, middleHead.next, right);
    }


    private ListNode findMiddle(ListNode head) {

        if (head == null) {
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;

    }

    private ListNode concat(ListNode left, ListNode middle, ListNode right) {

        ListNode dummy = new ListNode(0);
        dummy.next = left;
        left = dummy;

        while (left != null && left.next != null) {
            left = left.next;
        }


        left.next = middle;

        while (middle != null && middle.next != null) {
            middle = middle.next;
        }

        middle.next = right;

        return dummy.next;

    }

}