链表排序

leetCode-148 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

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

在 O(n log n) 时间复杂度排序中，有快速排序和归并排序。

使用归并排序

对链表找到中间点进行截断，知道截断只剩下一个元素，再进行合并。

合并时，建立一个临时链表，按顺序添加到临时链表中。

怎么找到链表的中间点：使用快慢指针，快指针每次走两步，满指针每次走一步。当快指针走到最后，慢指针所指向的链表节点就为中间节点。

注意：如果题目中给出的链表没有头结点，将设置一个头结点指向第一个节点，方便操作。

代码为：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        //设置一个头结点指向第一个节点
        ListNode node = new ListNode(-1);
        node.next = head;
        //快慢指针首先都指向头结点
        ListNode fast = node, slow = node;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow是将链表分为一半的节点位置，建立一个新链表存储中间节点后面的节点
        ListNode tmp = slow.next;
        //将中间节点作为切割，因此指向空节点
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        //临时链表存放排序后的节点
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

使用快速排序

快速排序就是找到一个基准值，进行链表的分割，创建一个临时链表，添加比基准值小的节点，另一个原先得链表都是大于等于基准值得节点，

再将原来得链表拼接到临时链表得后面，进行下次排序。

下次排序分别对基准值得左边和右边进行排序。

代码为：

class Solution {
public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        // 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。
        ListNode newHead=new ListNode(-1);
        newHead.next=head;
        return quickSort(newHead,null);
    }
    // 带头结点的链表快速排序
    private ListNode quickSort(ListNode head,ListNode end){
        if (head==end||head.next==end) return head;
        // 将小于划分点的值存储在临时链表中
        ListNode tmpHead=new ListNode(-1);
        // partition为划分点，p为链表指针，tp为临时链表指针
        ListNode partition=head.next,p=partition,tp=tmpHead;
        // 将小于划分点的结点放到临时链表中
        while (p.next!=end){
            if (p.next.val<partition.val){
                tp.next=p.next;
                tp=tp.next;
                p.next=p.next.next;
            }else {
                p=p.next;
            }
        }
        // 合并临时链表和原链表，将原链表接到临时链表后面即可
        tp.next=head.next;
        // 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了）
        head.next=tmpHead.next;
        quickSort(head,partition);
        quickSort(partition,end);
        // 题目要求不带头节点，返回结果时去除
        return head.next;
    }
}