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

发布于:2025-03-17 ⋅ 阅读:(16) ⋅ 点赞:(0)

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. 链表排序的常见方法

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

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

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


4. 归并排序(Merge Sort)

4.1 归并排序的思想

归并排序基于 分治法(Divide and Conquer)

  1. 分割(Divide): 将链表从中间拆分为两个子链表。
  2. 排序(Sort): 递归地对两个子链表进行排序。
  3. 合并(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 插入排序的思想

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

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

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²) 不推荐

选用建议

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

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