📚 课程目录第4章顺序表与链表实战

4. 顺序表与链表实战：动态扩容、单链表、双链表、循环链表与经典题目

线性表是数据结构中最基础、最核心的结构之一，在考研笔试与机试中占据举足轻重的地位。本章聚焦于顺序表与链表的实战构建与操作，重点剖析顺序表的动态扩容机制、单链表/双链表/循环链表的指针操作细节，并通过链表反转、合并有序链表等经典题目，帮助考生建立“结构设计→边界控制→复杂度分析”的完整解题链路。理解这两种存储结构的本质差异，是后续学习栈、队列、图论的基础，也是应对算法大题的关键能力。

上图从存储结构、访问方式、插入删除代价三个维度对比了顺序表与链表。顺序表依托连续内存，支持下标随机访问；链表依靠指针串联分散节点，擅长频繁插入删除。考生需要深刻理解：没有优劣，只有场景适配。下面从实战角度逐一拆解。

4.1 顺序表的动态扩容机制

4.1.1 核心原理

顺序表底层是数组，但静态数组长度固定，无法满足运行时数据量变化的需求。动态扩容的本质是：当元素个数达到容量上限时，申请一块更大的连续内存，将原数据拷贝过去，释放旧空间。考研中常考扩容策略的复杂度分析。

扩容策略	均摊时间复杂度	空间浪费	适用场景
固定增量（如每次+10）	O(n)	较小	数据量小且增长平稳
倍增（如×2）	O(1) 均摊	最多浪费一半	通用首选
黄金比例（×1.5）	O(1) 均摊	约1/3	内存敏感场景

  考研重点：倍增扩容的均摊分析——假设从容量1开始，每次扩容×2，插入n个元素的总拷贝次数为 1+2+4+...+n ≈ 2n，均摊到每次插入为 O(1)。这是“均摊复杂度”的经典证明，务必掌握。

4.1.2 操作流程与代码骨架

typedef struct {
    int *data;      // 指向动态数组
    int size;       // 当前元素个数
    int capacity;   // 当前容量
} SeqList;

void ensureCapacity(SeqList *L) {
    if (L->size < L->capacity) return;
    int newCap = (L->capacity == 0) ? 4 : L->capacity * 2;
    int *newData = (int *)malloc(sizeof(int) * newCap);
    for (int i = 0; i < L->size; i++) 
        newData[i] = L->data[i];   // 拷贝
    free(L->data);
    L->data = newData;
    L->capacity = newCap;
}

4.1.3 案例拆解：扩容的隐藏代价

某校机试题目要求实现一个动态数组，支持append操作。有考生采用“每次扩容+1”的策略，插入10万个元素时，总拷贝次数约为 1+2+3+...+100000 ≈ 5×10⁹，程序运行超时。而采用倍增策略，总拷贝次数约为 2×100000 = 2×10⁵，差距达万倍。这提醒我们：扩容策略直接影响程序性能，不能只关注功能正确。

常见误区：扩容后忘记释放旧内存导致内存泄漏；扩容时未初始化新空间导致脏数据；size与capacity混淆导致越界访问。

4.2 单链表的构建与核心操作

4.2.1 核心原理

单链表每个节点包含数据域和指针域（next），通过指针将节点串联。头节点（head）是链表的入口，尾节点的next指向NULL。单链表只能从前往后遍历，无法回溯。

4.2.2 关键操作流程

头插法：新节点next指向原头节点，更新头指针。时间复杂度O(1)，但元素顺序与插入顺序相反。
尾插法：需遍历到尾部（或维护尾指针），新节点next置NULL。时间复杂度O(n)，若维护尾指针可优化为O(1)。
删除节点：找到前驱节点，令其next指向待删节点的next，释放待删节点。
反转链表：三指针法（pre/cur/next）迭代，或递归实现。

// 单链表反转（迭代法）
ListNode* reverseList(ListNode* head) {
    ListNode *pre = NULL, *cur = head;
    while (cur) {
        ListNode *next = cur->next;  // 保存后继
        cur->next = pre;             // 反转指针
        pre = cur;                   // 前驱后移
        cur = next;                  // 当前后移
    }
    return pre;  // 新头节点
}

4.2.3 案例拆解：链表反转的边界控制

题目：反转从位置m到n的链表（LeetCode 92）。关键步骤：先找到第m-1个节点（pre），然后对m到n区间内的节点执行局部反转，最后将pre的next指向反转后的头，区间尾节点指向原第n+1个节点。常见错误：未处理m=1时头节点变化的情况；反转后未正确连接pre与区间新头。建议使用虚拟头节点（dummy）统一处理边界。

实战技巧：涉及头节点可能变化的操作（反转、删除、插入），优先使用虚拟头节点，避免分类讨论。

4.3 双链表与循环链表

4.3.1 双链表：空间换时间

双链表节点包含prior和next两个指针，支持双向遍历。删除节点时无需找前驱，直接通过prior指针操作。代价是每个节点多一个指针域，内存开销增加。

操作	单链表	双链表
删除已知节点	O(n) 需找前驱	O(1) 直接操作
反向遍历	需反转或递归	O(n) 直接prior
内存开销	1个指针/节点	2个指针/节点

4.3.2 循环链表：首尾相连

循环链表将尾节点的next指向头节点（或头指针），形成环。优点：从任意节点出发都能遍历全表；适合约瑟夫环、循环队列等场景。注意：遍历终止条件从 p != NULL 变为 p != head，防止死循环。

4.3.3 案例：约瑟夫环问题

n个人围成一圈，从第k个人开始报数，报到m的人出列，求最后幸存者。使用循环链表模拟：每次从当前节点出发，移动m-1步，删除该节点，继续下一轮。时间复杂度O(n×m)。若n=10⁵、m=10⁵，直接模拟会超时，需用数学递推（约瑟夫环公式）优化为O(n)。这提示我们：数据结构是工具，算法优化才是核心。

4.4 经典题目：合并有序链表

4.4.1 题目描述与思路

将两个升序链表合并为一个新的升序链表。核心思路：双指针比较 + 尾插法。维护两个指针分别指向两个链表头部，每次取较小值接入结果链表，直到某一链表为空，将剩余部分直接拼接。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);   // 虚拟头节点
    ListNode *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.4.2 案例拆解：递归与迭代的取舍

递归版本代码更简洁：merge(l1,l2) = l1->val < l2->val ? l1->next=merge(l1->next,l2) : l2->next=merge(l1,l2->next)。但递归深度等于链表长度，当链表很长（如10⁵）时可能栈溢出。迭代版本空间O(1)，更稳健。考研机试中，优先选择迭代实现，避免递归深度风险。

  复杂度分析：合并两个长度分别为m、n的有序链表，时间复杂度O(m+n)，空间复杂度O(1)（迭代）。这是最优解，无法再优化。

4.5 常见误区与总结复盘

误区	后果	正确做法
链表操作未处理空指针	程序崩溃	操作前判断 p != NULL
顺序表扩容后未更新capacity	越界访问	同步更新size与capacity
循环链表遍历条件错误	死循环	用 do-while 或记录起始节点
反转链表丢失next指针	链表断裂	先保存后继再改指针
合并链表时未用虚拟头	头节点处理繁琐	统一使用dummy简化逻辑

总结：本章核心在于指针操作的严谨性与结构选择的场景意识。顺序表适合读多写少、需要随机访问的场景；链表适合写多读少、无法预知数据量的场景。动态扩容的均摊分析、链表反转的指针变换、合并有序链表的双指针技巧，是考研的高频考点。建议考生在纸上手动模拟指针变化过程，再动手编码，做到“手到、眼到、心到”。