链表排序算法总结

概述

问题描述：给定一个链表，请将这个链表升序排列。

• 节点定义：

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

1 链表插入排序

题目描述：Leetcode 0147 链表进行插入排序

分析

• 因为头结点可能会改变，因此需要设置一个虚拟头结点dummy。

• 我们从前向后遍历整个链表，假设当前考察节点为p，我们需要从dummy开始遍历，找到第一个大于p->val的前一个节点cur，然后将p插入到cur后面。

代码

• C++

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummy = new ListNode(-1);
        for (auto p = head; p; ) {
            auto cur = dummy, next = p->next;  // next是下一个需要考察的节点
            while (cur->next && cur->next->val <= p->val) cur = cur->next;
            p->next = cur->next;
            cur->next = p;
            p = next;
        }
        return dummy->next;
    }
};

时空复杂度分析

• 时间复杂度：$O(n^2)$，n为链表长度。

• 空间复杂度：$O(1)$。

2 链表归并排序

题目描述：Leetcode 0148 排序链表

分析

• 因为要求时间O(1)，因此就不能使用递归的写法，这一题可以使用归并排序的迭代写法（自底向上）。

• 这一题十分类似于Leetcode 0023 合并K个有序链表，我们可以使用LC23的思路求解。代码中的变量如下图所示：

• 上面的做法用C++演示。

• 用Java演示一下递归（自顶向下）的写法，但是空间复杂度不是$O(1)$的。关键在于找到链表的中点，与Leetcode 0109 将有序链表转换二叉搜索树类似，这两题都需要找到中点，不同于LC109，LC109的终止条件是f != null && f->next != null，这里使用的终止条件是f.next != null && f->next->next != null，两者的区别为：

• 之后从s后截成两段，进行递归求解即可。

• 合并两个有序链表可以使用Leetcode 0021 合并两个有序链表的方法。

代码

• C++

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        for (auto p = head; p; p = p->next) n++;  // 求出节点数目

        for (int len = 1; len < n; len += len) {  // 枚举合并长度
            // 下面循环一次代表向上递推一层
            auto dummy = new ListNode(-1), cur = dummy;  // 因为头结点可能变，因此需要虚拟头结点
            for (int j = 1; j <= n; j += 2 * len) {  // 枚举待合并链表的起点, j不会再下面用到
                auto p = head, q = head;
                for (int i = 0; i < len && q; i++) q = q->next;
                auto o = q;  // o为下次合并的起点
                for (int i = 0; i < len && o; i++) o = o->next;
                // 归并p、q开头的链表
                int l = 0, r = 0;
                while (l < len && r < len && p && q)    
                    if (p->val <= q->val) cur = cur->next = p, p = p->next, l++;
                    else cur = cur->next = q, q = q->next, r++;
                while (l < len && p) cur = cur->next = p, p = p->next, l++;
                while (r < len && q) cur = cur->next = q, q = q->next, r++;
                head = o;  // 进行后面两段链表的合并
            }
            cur->next = NULL;
            head = dummy->next;
        }
        return head;
    }
};

• Java

class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 快慢指针，寻找中间点
        ListNode s = head, f = head;
        while (f.next != null && f.next.next != null) {
            s = s.next; f = f.next.next;
        }
        ListNode newHead = s.next;
        s.next = null;  // 断开链表，分成前后两部分

        ListNode left = sortList(head), right = sortList(newHead);
        return merge(left, right);  // 返回合并后的链表头指针
    }
}

时空复杂度分析

• 时间复杂度：$O(n\times log(n))$，n为链表长度。

• 空间复杂度：C++： $O(1)$。Java：$O(log(n))$。

3 链表快速排序

题目描述：AcWing 1451. 单链表快速排序

分析

• 使用三个虚拟头指针left, mid, right，记录每次partition的结果，这里取头结点val的值作为分界线。

• 递归的过程中，我们每次都要遍历整个链表，对节点值小于val的节点接到left中，节点值等于val的节点接到mid中，节点值大于val的节点接到right中，之后还要将三个链表的尾结点置为空。

• 接着递归处理left、right，递归结束后将三段拼接起来即可。

代码

• C++

class Solution {
public:
    ListNode* quickSortList(ListNode* head) {
        
        if (!head || !head->next) return head;
        
        auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
        auto ltail = left, mtail = mid, rtail = right;
        int val = head->val;
        
        for (auto p = head; p; p = p->next) {
            if (p->val < val) ltail = ltail->next = p;
            else if (p->val == val) mtail = mtail->next = p;
            else rtail = rtail->next = p;
        }
        
        ltail->next = mtail->next = rtail->next = NULL;
        left->next = quickSortList(left->next);
        right->next = quickSortList(right->next);
        
        // 拼接三个链表
        get_tail(left)->next = mid->next;
        get_tail(mid)->next = right->next;
        
        auto p = left->next;
        
        delete left;
        delete mid;
        delete right;
        
        return p;
    }
    
    // 获取链表的尾节点
    ListNode* get_tail(ListNode* head) {
        while (head->next) head = head->next;
        return head;
    }
};

时空复杂度分析

• 时间复杂度：$O(n\times log(n))$，n为链表长度。

• 空间复杂度：$O(log(n))$。