C++ 链表与排序：详解及实现-EW帮帮网

1. 引言

链表（Linked List）是一种常见的数据结构，支持动态内存分配，适用于插入和删除操作频繁的场景。而排序（Sorting）是计算机科学中的重要算法之一，不同的排序算法适用于不同的数据结构。本篇文章将介绍 链表的基本概念、常见排序算法 以及 如何对链表进行排序。

2. 链表基础

2.1 链表的定义

链表由一系列节点（Node）组成，每个节点包含两部分：

val：存储数据。
next：指向下一个节点的指针。

单链表（Singly Linked List）的基本结构如下：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

双向链表（Doubly Linked List）还包含 prev 指针，指向前一个节点。

3. 链表排序的常见方法

对链表进行排序的常见方法包括：

归并排序（Merge Sort） - 适用于链表，时间复杂度 O(n log n)。
快速排序（Quick Sort） - 可用于链表，但需要额外优化。
插入排序（Insertion Sort） - 适用于部分有序链表，时间复杂度 O(n²)。
冒泡排序（Bubble Sort） - 不适用于链表，时间复杂度 O(n²)。

我们主要讨论适用于链表的 归并排序 和 插入排序。

4. 归并排序（Merge Sort）

4.1 归并排序的思想

归并排序基于 分治法（Divide and Conquer）：

分割（Divide）： 将链表从中间拆分为两个子链表。
排序（Sort）： 递归地对两个子链表进行排序。
合并（Merge）： 使用 合并两个有序链表 的方法，将两个子链表合并成一个有序链表。

4.2 代码实现

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // 使用快慢指针找到链表的中点
        ListNode* slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* mid = slow->next;
        slow->next = nullptr; // 断开链表
        
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        
        return merge(left, right);
    }
    
private:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummy(0), *tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

4.3 复杂度分析

时间复杂度： O(n log n)
空间复杂度： O(log n)（递归栈）

5. 插入排序（Insertion Sort）

5.1 插入排序的思想

插入排序适用于部分有序的链表。基本思想：

维护一个有序链表部分，逐个插入未排序部分的节点。
采用 哨兵节点 简化插入逻辑。

5.2 代码实现

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode dummy(0);
        ListNode* pre = &dummy;
        dummy.next = head;
        ListNode* cur = head;
        
        while (cur->next) {
            if (cur->next->val >= cur->val) {
                cur = cur->next;
                continue;
            }
            
            ListNode* temp = cur->next;
            cur->next = temp->next;
            
            pre = &dummy;
            while (pre->next->val < temp->val) {
                pre = pre->next;
            }
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummy.next;
    }
};

5.3 复杂度分析

时间复杂度： O(n²)
空间复杂度： O(1)

6. 总结

排序算法	时间复杂度	适用场景
归并排序	O(n log n)	适用于任何链表
快速排序	O(n log n)	不太适合链表（需要额外优化）
插入排序	O(n²)	适用于部分有序链表
冒泡排序	O(n²)	不推荐

选用建议

若链表长度较大，推荐 归并排序。
若链表大部分已经有序，可选择 插入排序。

以上是关于 链表排序 的详细解析，希望对你有所帮助！

C++ 链表与排序：详解及实现