题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例

示例1：

1 2	输入: 4->2->1->3 输出: 1->2->3->4

示例2：

1 2	输入: -1->5->3->4->0 输出: -1->0->3->4->5

思路

有两种方法：快速排序和归并排序

快速排序的重点和难点是如何根据基准点（这里以头结点为基准）将元素分为两半

归并排序要先利用快慢指针找到中点，根据中点划分为两半，对这两半分别归并排序后，进行合并即可

代码实现

链表节点的定义：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

快速排序：

/**
 * 排序范围：从head节点开始，到tail的前一个结点（不包括tail，这样比较好处理）
 */
private void quickSort(ListNode head, ListNode tail) {
    if (head == tail || head.next == tail) {
        return;
    }

    int pivot = head.val;       //基准值
    ListNode center = head;
    ListNode curr = head.next;
    while (curr != tail) {
        if (curr.val < pivot) {
            center = center.next;
            swap(center, curr);
        }
        curr = curr.next;
    }

    //最终在center左边的是比基准值小的
    swap(head, center);

    quickSort(head, center);
    quickSort(center.next, tail);
}

/**
 * 交换两节点的值
 */
private void swap(ListNode L1, ListNode L2) {
    int temp = L1.val;
    L1.val = L2.val;
    L2.val = temp;
}

归并排序：

private ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    //先利用快慢指针找到中点
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode right = mergeSort(slow.next);  //排好右半部分
    slow.next = null;
    ListNode left = mergeSort(head);        //排好左半部分

    return merge(left, right);
}

/**
 * 合并两个已排好序的链表
 */
private ListNode merge(ListNode L1, ListNode L2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (L1 != null && L2 != null) {
        if (L1.val < L2.val) {
            curr.next = L1;
            curr = L1;
            L1 = L1.next;
        } else {
            curr.next = L2;
            curr = L2;
            L2 = L2.next;
        }
    }
    if (L1 != null) {
        curr.next = L1;
    } else {
        curr.next = L2;
    }

    return dummy.next;
}