408

数据结构

DS-02-04 线性表的应用（合并/逆置/去重等）

---

一、定位信息

项目	内容
所属圈层	核心层
考点热度	H级（高频重点） — 线性表应用题是408大题的常客，合并、去重、查找等算法设计题近5年反复出现
前置知识回顾	需掌握顺序表操作（DS-02-02）、链表操作（DS-02-03），特别是双指针、头插法、尾插法等基本技巧
知识网络定位	本单元是线性表章节的综合应用层，将前3个单元的基础操作组合为解决实际问题的算法，也是后续排序（第7章）和查找（第6章）算法的思维基础

---

二、知识点讲解

2.1 线性表应用的命题规律

408考试中，线性表应用题的核心考法是：给定一个具体问题，要求设计算法并在限定时间/空间复杂度内解决。常见问题类型包括：

问题类型	典型描述	核心技巧
合并	将两个有序表合并为一个有序表	双指针归并
去重	删除表中重复元素	排序后扫描 / 哈希 / 双指针
逆置	将表中元素顺序反转	头插法 / 首尾交换
查找	找第k小/倒数第k个等	双指针 / 快慢指针
分割	按条件将元素分为两部分	双指针分区
交/并/差	求两个集合的交集、并集、差集	归并思想

2.2 有序表合并（核心算法）

问题：将两个递增有序的顺序表 $A$（$m$ 个元素）和 $B$（$n$ 个元素）合并为一个递增有序的顺序表 $C$。

算法思路：归并思想——用两个指针分别扫描 $A$ 和 $B$，每次取较小者放入 $C$。

// 合并两个递增有序顺序表A和B，结果存入C（C空间需足够大）
bool Merge(SqList A, SqList B, SqList &C) {
    if (A.length + B.length > MaxSize)  // ① 检查C的空间是否足够
        return false;
    int i = 0, j = 0, k = 0;           // ② i扫描A，j扫描B，k指向C的末尾
    while (i < A.length && j < B.length) {  // ③ 两个表都没扫完
        if (A.data[i] <= B.data[j])    // ④ 取A和B中较小者
            C.data[k++] = A.data[i++];
        else
            C.data[k++] = B.data[j++];
    }
    while (i < A.length)               // ⑤ A有剩余，全部放入C
        C.data[k++] = A.data[i++];
    while (j < B.length)               // ⑥ B有剩余，全部放入C
        C.data[k++] = B.data[j++];
    C.length = k;                      // ⑦ 设置C的长度
    return true;
}

时间复杂度：$O(m + n)$ — 每个元素最多被比较一次。 空间复杂度：$O(m + n)$（结果表 $C$ 的空间）。

2.3 有序链表合并（408高频考点）

问题：将两个递增有序的单链表 $A$ 和 $B$ 合并为一个递增有序的单链表 $C$（不新建结点，直接拼接）。

// 合并两个递增有序单链表，结果链表使用A和B的结点（尾插法）
LinkList MergeList(LinkList A, LinkList B) {
    LNode *pa = A->next;               // ① pa指向A的第一个数据结点
    LNode *pb = B->next;               // ② pb指向B的第一个数据结点
    LNode *r = A;                      // ③ r指向结果链表的尾结点（复用A的头结点）
    
    while (pa != NULL && pb != NULL) {  // ④ 两个链表都没扫完
        if (pa->data <= pb->data) {    // ⑤ 取较小者
            r->next = pa;              // ⑥ 尾插法：接上pa
            r = pa;                    // ⑦ 更新尾指针
            pa = pa->next;             // ⑧ pa后移
        } else {
            r->next = pb;              // ⑥' 尾插法：接上pb
            r = pb;                    // ⑦'
            pb = pb->next;             // ⑧'
        }
    }
    r->next = (pa != NULL) ? pa : pb;  // ⑨ 剩余部分直接接上
    free(B);                           // ⑩ 释放B的头结点
    return A;
}

时间复杂度：$O(m + n)$空间复杂度：$O(1)$（不新建结点，只修改指针）

2.4 顺序表去重（原地算法）

问题：从递增有序顺序表中删除所有重复元素，使每个元素只出现一次。

// 有序顺序表去重（原地，时间O(n)，空间O(1)）
void DeleteDuplicate(SqList &L) {
    if (L.length <= 1) return;         // ① 空表或单元素无需处理
    int k = 0;                         // ② k指向新表末尾（慢指针）
    for (int i = 1; i < L.length; i++) { // ③ i从第二个元素开始遍历（快指针）
        if (L.data[i] != L.data[k]) { // ④ 若当前元素与新表末尾不同
            k++;                       // ⑤ 新表末尾后移
            L.data[k] = L.data[i];    // ⑥ 将当前元素放入新表末尾
        }
        // 若相同，跳过（删除重复）
    }
    L.length = k + 1;                 // ⑦ 更新表长
}

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

关键点：利用有序性——重复元素一定相邻，只需比较相邻元素即可。

2.5 无序表去重（两种方法对比）

对于无序顺序表的去重问题，有序表的方法不适用。需要选择合适的方法：

方法	前提条件	时间复杂度	空间复杂度
先排序再去重	允许改变元素顺序	$O(n\log n)$	$O(1)$
哈希表法	有足够空间	$O(n)$	$O(n)$
双重循环法	无特殊要求	$O(n^2)$	$O(1)$

2.6 求两个顺序表的交集

问题：已知两个递增有序顺序表 $A$ 和 $B$，求它们的公共元素构成的新表 $C$。

// 求有序顺序表A和B的交集，存入C
void Intersection(SqList A, SqList B, SqList &C) {
    int i = 0, j = 0, k = 0;           // ① 双指针初始化
    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j])     // ② A的元素较小，A指针后移
            i++;
        else if (A.data[i] > B.data[j]) // ③ B的元素较小，B指针后移
            j++;
        else {                          // ④ 相等，是公共元素
            C.data[k++] = A.data[i];   // ⑤ 放入C
            i++; j++;                   // ⑥ 两个指针都后移
        }
    }
    C.length = k;                      // ⑦ 设置C的长度
}

时间复杂度：$O(m + n)$

---

三、记忆与理解辅助

技巧1：归并类算法的通用框架

所有有序表的合并、交集、差集算法都遵循同一个框架：

双指针i, j分别扫描两个表
while (两个表都没扫完) {
    比较当前元素大小
    根据比较结果移动指针并决定是否输出
}
处理剩余元素

记住这个框架，具体的"交/并/差"只需改比较分支中的操作。

技巧2：双指针技巧分类

双指针类型	典型应用	核心思想
对撞指针	有序数组两数之和	一头一尾，向中间靠拢
快慢指针	链表判环、找中间结点	快指针走两步，慢指针走一步
归并指针	有序表合并、交集、差集	两表各一个指针，比较后移动
滑动窗口	子数组/子串问题	左右边界同步或异步移动

技巧3：算法题解题"四步法"

面对408线性表算法设计题，按以下步骤思考：

1. 审题：明确输入输出、数据特征（有序/无序）、约束条件（时间/空间复杂度）
2. 选型：根据数据特征选择合适的方法（有序→归并/双指针，无序→排序+扫描/哈希）
3. 设计：写出伪代码，注意边界条件（空表、单元素、头尾结点）
4. 验证：用小规模数据手动模拟，检查正确性

技巧4：有序 vs 无序处理策略对比

操作	有序表	无序表
去重	相邻比较 $O(n)$	排序+扫描 $O(n\log n)$ 或哈希 $O(n)$
查找	折半查找 $O(\log n)$	顺序查找 $O(n)$
合并	归并 $O(m+n)$	先排序再归并 $O((m+n)\log(m+n))$
交集	归并 $O(m+n)$	哈希 $O(m+n)$

---

四、例题与精解

例题1（基础）

命题意图：考查有序链表合并算法的实现。

题目：已知两个递增有序单链表 $A$ 和 $B$，合并为一个递减有序单链表 $C$（使用头插法），不新建结点。

审题分析：

• 输入：两个递增有序链表
• 输出：一个递减有序链表
• 要求：不新建结点（复用A和B的结点）
• 关键：递增→递减，提示用头插法

解题思路：由于结果是递减的，而两个输入都是递增的，用头插法建结果链表。同时用归并思想比较两个链表的当前元素，取较大者进行头插（因为头插会反转顺序）。

完整步骤：

// 合并两个递增有序链表为一个递减有序链表（头插法，不新建结点）
LinkList MergeDesc(LinkList A, LinkList B) {
    LNode *pa = A->next;               // ① pa指向A的第一个数据结点
    LNode *pb = B->next;               // ② pb指向B的第一个数据结点
    LNode *r = NULL;                   // ③ r用于暂存下一个待处理结点
    
    A->next = NULL;                    // ④ 初始化结果链表（复用A的头结点）
    
    while (pa != NULL && pb != NULL) {  // ⑤ 归并过程
        if (pa->data <= pb->data) {    // ⑥ 取较小者（为了最终递减，需从最小的开始头插）
            r = pa->next;              // ⑦ 保存后继
            pa->next = A->next;        // ⑧ 头插法：pa指向原第一个结点
            A->next = pa;              // ⑨ 头结点指向pa
            pa = r;                    // ⑩ pa移到下一个
        } else {
            r = pb->next;              // ⑦'
            pb->next = A->next;        // ⑧'
            A->next = pb;              // ⑨'
            pb = r;                    // ⑩'
        }
    }
    // ⑪ 处理剩余结点（同样用头插法）
    while (pa != NULL) {
        r = pa->next;
        pa->next = A->next;
        A->next = pa;
        pa = r;
    }
    while (pb != NULL) {
        r = pb->next;
        pb->next = A->next;
        A->next = pb;
        pb = r;
    }
    free(B);                           // ⑫ 释放B的头结点
    return A;
}

验证：$A = (1, 3, 5)$，$B = (2, 4, 6)$

步骤	取出	头插后C的状态
初始	—	空
⑥取1	1	1
⑥取2	2	2→1
⑥取3	3	3→2→1
⑥取4	4	4→3→2→1
⑥取5	5	5→4→3→2→1
⑥取6	6	6→5→4→3→2→1

结果 $C = (6, 5, 4, 3, 2, 1)$ ✅ 递减有序

方法反思：

• 核心技巧：归并 + 头插法 = 递增输入变递减输出
• 易错点：头插法中必须先保存后继（r = pa->next），否则会丢失后续结点
• 变式：若要递增输出，用尾插法即可

---

例题2（中等）

命题意图：综合考查双指针、链表操作和算法设计能力。

题目：给定一个带头结点的单链表 $L$（$n$ 个元素），设计一个时间复杂度为 $O(n)$ 的算法，找出链表中倒数第 $k$ 个结点（$1 \leq k \leq n$），并返回该结点的指针。

审题分析：

• 输入：带头结点的单链表 $L$，正整数 $k$
• 输出：倒数第 $k$ 个结点的指针
• 约束：时间 $O(n)$，只能遍历一次链表
• 难点：链表不能从后往前遍历，且只能遍历一次（不能先数长度再找）

解题思路：快慢双指针法——让快指针先走 $k$ 步，然后快慢指针同时走，当快指针到达末尾时，慢指针恰好指向倒数第 $k$ 个结点。

完整步骤：

// 找到单链表中倒数第k个结点（快慢指针法，一趟扫描）
LNode *FindKthFromEnd(LinkList L, int k) {
    LNode *fast = L->next;             // ① fast快指针，指向第一个数据结点
    LNode *slow = L->next;             // ② slow慢指针，指向第一个数据结点
    
    // ③ fast先走k步
    for (int i = 0; i < k; i++) {
        if (fast == NULL)              // ④ k大于链表长度，不合法
            return NULL;
        fast = fast->next;             // ⑤ fast前进一步
    }
    
    // ⑥ fast和slow同时走，直到fast到达末尾
    while (fast != NULL) {
        fast = fast->next;             // ⑦ fast前进一步
        slow = slow->next;             // ⑧ slow前进一步
    }
    
    return slow;                       // ⑨ 此时slow指向倒数第k个结点
}

图示验证（$L = (1, 2, 3, 4, 5)$，$k = 2$，目标：倒数第2个 = 4）：

步骤	fast位置	slow位置	说明
初始	1	1	都在第一个结点
fast走k=2步	3	1	fast走了2步
同时走第1步	4	2
同时走第2步	5	3
同时走第3步	NULL	4	fast到末尾，停止

返回 slow = 结点4 ✅

复杂度分析：

• 时间：只遍历一次链表，$T(n) = O(n)$ ✅
• 空间：只用两个指针，$S(n) = O(1)$ ✅

方法反思：

• 快慢指针法是链表问题的万能工具之一，适用于：找中间结点（快走2慢走1）、判环（快慢相遇则有环）、找倒数第k个（快先走k步）
• 这道题的陷阱：如果不允许遍历两次（先求长度再找），就必须用快慢指针
• 变式：找链表的中间结点——fast每次走2步，slow每次走1步，fast到末尾时slow在中间

---

五、考情分析

分析维度	说明
考查频次	线性表应用类题目近5年出现频率高，几乎每年都有1道大题涉及链表或顺序表的算法设计
常见题型	大题为主（8–12分），少数作为选择题（2分）考查思路判断
分值占比	约6–12分
命题趋势	命题方向越来越注重"最优复杂度"和"原地算法"要求；双指针技巧是绝对高频考点；近年出现过"链表判环"、"两个链表的公共结点"、"链表排序"等综合题

---

六、易错点提醒

易错点1

• 错误表现：合并有序链表时使用头插法，忘记结果会变成逆序
• 错误原因：没有意识到头插法的"反转"特性
• 正确做法：若要保持递增顺序，必须用尾插法；若题目要求递减，才用头插法。审题时务必看清输出要求

易错点2

• 错误表现：快慢指针法中，快指针先走 $k$ 步时没有检查是否越界
• 错误原因：假设 $k$ 一定合法，不考虑 $k > n$ 的情况
• 正确做法：在快指针先走 $k$ 步的循环中，每步都要检查 fast != NULL，若中途为NULL说明 $k$ 超过链表长度

易错点3

• 错误表现：去重算法中，删除结点后没有更新指针，导致遍历断裂
• 错误原因：对链表删除操作的指针变化不够熟练
• 正确做法：删除结点后，遍历指针应指向删除结点的后继（而非继续后移），因为后继可能是新的重复元素

易错点4

• 错误表现：算法设计题中不写边界条件处理（空表、单元素、k=0等）
• 错误原因：只关注核心逻辑，忽略特殊情况
• 正确做法：408评分标准中，边界处理通常占1–2分。至少要处理：空表返回特殊值、$k$ 不合法时返回错误、单元素表的特殊情况

易错点5

• 错误表现：合并顺序表时忘记更新结果表的 length
• 错误原因：只关注数据复制，忘记维护表的元信息
• 正确做法：所有修改顺序表的算法，最后都要更新 L.length。这是408大题中常见的扣分点

---

七、来源标注

• 依据2026考研统考大纲——数据结构部分"线性表的应用"
• 依据《数据结构（C语言版）》严蔚敏版第二章
• 依据《数据结构》王道考研辅导讲义
• 依据历年408统考真题命题规律分析