题目描述

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(nlogn)

Java 代码

class Solution {
    // 目的是使得左边的值都小于pivot，右边的值都不小于pivot
    // 所以用一个索引记录左边的坐标，遍历过程中，每次碰到比pivot小的，都要交换一下，放到左边。
    // 遍历完成后，再把pivot交换到中间来，这样就达成了目的。

    // 10 -> 2 -> 50 -> 3 -> 20
    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }

    private void quickSort(ListNode head, ListNode tail) {
        if (head == tail || head.next == tail) {
            return;
        }

        int pivot = head.val;
        ListNode p = head, q = head.next;
        while (q != tail) {
            if (q.val < pivot) {
                p = p.next;
                swap(p, q);
            }
            q = q.next;
        }

        swap(head, p);
        quickSort(head, p);
        quickSort(p.next, tail);
    }

    private void swap(ListNode a, ListNode b) {
        int t = a.val;
        a.val = b.val;
        b.val = t;
    }
}