Sort List

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

Example:

Given 1->3->2->null, sort it to 1->2->3->null.

Challenge:

Solve it by merge sort & quick sort separately.

Solution:

Since the time complexity is O(nlogn). There are only two ways could solve this problem, merge sort and quick sort.

Notes for merge sort:

1. No need for extra space, since linked list can be connected or disconnected in O(1).
2. Splitting list is much harder. Instead of calculating middle index, we need to use two pointers to find the node who is previous to middle node. Then set the next of previous middle node to null and return middle node.

Notes for quick sort:

1. We still need to use two pointers to find the pivot which is the value in middle node
2. Then we create three linked lists: left list (all nodes with value that is smaller than pivot), middle list (all nodes with value that equals to pivot), right list (all nodes with value that is larger than pivot).
3. After recursive quick sort for left list and right list, we then merge all these three linked lists by attachedToTail.

Code:

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
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) {  
        if (head == null) {
            return head;
        }
        return quickSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = split(head);
        ListNode node1 = mergeSort(head);
        ListNode node2 = mergeSort(newHead);
        return merge(node1, node2);
    }

    //MergeSort
    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0);
        ListNode left = node1;
        ListNode right = node2;
        ListNode cur = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                cur.next = left;
                cur = cur.next;
                left = left.next;
            } else {
                cur.next = right;
                cur = cur.next;
                right = right.next;
            }
        }
        while (left != null) {
            cur.next = left;
            cur = cur.next;
            left = left.next;
        }
        while (right != null) {
            cur.next = right;
            cur = cur.next;
            right = right.next;
        }
        return dummy.next;
    }

    private ListNode split(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        prev.next = null;
        return slow;
    }

    //Quick Sort
    private ListNode quickSort(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        int pivot = middle(node).val;
        ListNode leftStart = new ListNode(0);
        ListNode middleStart = new ListNode(0);
        ListNode rightStart = new ListNode(0);
        ListNode left = leftStart;
        ListNode middle = middleStart;
        ListNode right = rightStart;
        while (node != null) {
            if (node.val < pivot) {
                left.next = node;
                left = left.next;
            } else if (node.val > pivot) {
                right.next = node;
                right = right.next;
            } else {
                middle.next = node;
                middle = middle.next;
            }
            node = node.next;
        }
        left.next = null;
        right.next = null;
        middle.next = null;
        leftStart.next = quickSort(leftStart.next);
        rightStart.next = quickSort(rightStart.next);
        appendToTail(middleStart, rightStart.next);
        appendToTail(leftStart, middleStart.next);
        return leftStart.next;
    }

    private void appendToTail(ListNode head, ListNode node) {
        while (head.next != null) {
            head = head.next;
        }
        head.next = node;
    }

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