148. Sort List

Leetcode Linked List Sort

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

分析

排序链表，要求空间复杂度为$O(1)$，时间复杂度为$O(n\log n)$。既然要排序，很容易想到常见的排序方法，符合时间复杂度和空间复杂度的排序有快速排序和归并排序。

对于归并排序，把链表拆分成子链表，递归排序子链表，然后再合并链表。链表与数组不同，不能直接索引。为了表示子链表，一种方法是子链表在链表中的首尾位置，另一种更简单的方法是直接用子链表的首部位置表示，而将尾部位置设置为null。这是关键的一步，可以节省很多不必要的麻烦。链表的分割可参考LeetCode 21. Merge Two Sorted Lists，链表的中点可参考LeetCode 876. Middle of the Linked List。

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode mid = midList(head);
    ListNode right = sortList(mid.next);     // sort right half
    mid.next = null;
    ListNode left = sortList(head);          // sort left half
    return merge(left, right);
}

// merge linkedlist l1 nad l2
private ListNode merge(ListNode left, ListNode right) {
    // find head of the linkedlist after sorted
    ListNode head, pos;
    if (left.val < right.val) { head = left; left = left.next; }
    else {head = right; right = right.next; }
    pos = head;

    // iterate the linked list, link smaller element to head
    while (left != null &&  right != null) { // both iterate to the end of list
        if (left.val < right.val) { pos.next = left; left = left.next;}
        else {pos.next = right; right = right.next;}
        pos = pos.next;
    }

    // add remaining linkedlist
    pos.next = left != null ? left : right;
    return head;
}

// find middle node of given linkedlist
private ListNode midList(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

使用快速排序，比归并排序复杂，原因至少有以下几点

• 无法访问链表的前一个节点，也就意味着传统的partition方法在这里不适用，在partition时，只能将小于pivot的节点插入到pivot前面，将大于pivot的节点插入到pivot后面。
• 传统的快速排序通过shuffle来保证平均时间复杂度，这里也不能适用。
• 插入元素的时候，不能适用dummy node，因为空间复杂度必须为$O(1)$，论坛上好多快速排序的答案都不符合要求。

public ListNode sortList(ListNode head) {
    return quickSort(head, null);
}

public ListNode quickSort(ListNode begin, ListNode end) {
    // quit condition: only one node
    if (begin == end) return begin;
    ListNode head = partition(begin, end);      // partition, result: head .... begin...end
    ListNode h1 = quickSort(head, begin);       // sort left part, result: h1... head....
    ListNode h2 = quickSort(begin.next, end);   // sort right part, result: h2... begin.next...
    begin.next = h2;
    return h1;
}

// use begin as pivot:
// left to the begin is less than pivot, right to the begin is larger than pivot
ListNode partition(ListNode begin, ListNode end) {
    // head is the head, cur is currently visiting node, pre is the node before cur.
    ListNode head = begin, pre = head, cur = pre.next;
    int pivotValue = head.val; //pivot value
    while (cur != end) {
        // insert current node before head if it's value is less than pivot
        if (cur != null && cur.val < pivotValue) {
            pre.next = cur.next;
            cur.next = head;
            head = cur;
        } else {
            pre = cur;
        }
        cur = pre.next;
    }

    return head;
}