在正式学习之前先通过下表从时间复杂度、空间复杂度和适用场景三个维度对比循环链表、双向链表与线性表合并三种操作便于建立整体认知。操作时间复杂度空间复杂度适用场景循环链表创建与遍历创建 O(n)遍历 O(n)O(n)需要从任意节点出发循环访问全部元素如约瑟夫环、循环队列、操作系统进程调度等场景。双向链表创建、插入、删除与遍历创建 O(n)插入/删除 O(1)已知节点位置遍历 O(n)O(n)需要频繁在已知节点前后进行插入、删除操作或需要双向遍历的场景如 LRU 缓存、浏览器前进后退等。线性表合并两个有序表O(m n)O(m n)将两个有序线性表合并为一个有序表如归并排序的合并过程、多路归并、有序数据归并等场景。1、循环链表1.1 C 实现下面给出一个 C 实现循环链表创建与遍历的完整示例包含关键步骤注释。#include iostream // 定义循环链表节点结构 struct Node { int data; // 数据域 Node *next; // 指针域指向下一个节点 Node(int val) : data(val), next(nullptr) {} // 构造函数初始化节点 }; // 创建循环链表根据数组元素构建带头节点的循环链表 Node* createList(int arr[], int n) { Node *head new Node(0); // 创建头节点 head-next head; // 头节点先指向自身形成空循环 Node *tail head; // tail 始终指向最后一个节点 for (int i 0; i n; i) { Node *newNode new Node(arr[i]); // 为新元素分配节点 newNode-next head; // 新节点指向头节点保持循环 tail-next newNode; // 尾节点指向新节点 tail newNode; // 更新尾节点 } return head; } // 遍历循环链表从头节点的下一个节点开始直到回到头节点 void traverseList(Node *head) { Node *p head-next; // 从第一个数据节点开始 while (p ! head) { // 回到头节点说明遍历完成 std::cout p-data ; p p-next; } std::cout std::endl; } int main() { int arr[] {10, 20, 30, 40, 50}; Node *head createList(arr, 5); // 创建循环链表 traverseList(head); // 遍历并输出10 20 30 40 50 return 0; }1.2 408 伪代码考研 408 数据结构中循环链表的创建与遍历通常以伪代码形式考查重点在于理解指针操作和循环终止条件。下面给出符合 408 风格的伪代码版本。// 循环链表创建带头节点 // 输入数组 A[1..n]n 为元素个数 // 输出带头节点的循环链表 L CreateList(L, A, n) L new Node // 创建头节点 L-next L // 头节点先指向自身形成空循环 tail L // tail 指向尾节点 for i 1 to n p new Node // 为新元素分配节点 p-data A[i] // 写入数据 p-next L // 新节点指向头节点保持循环 tail-next p // 尾节点指向新节点 tail p // 更新尾节点 end for return L // 循环链表遍历 // 输入带头节点的循环链表 L // 输出依次输出各数据节点的值 TraverseList(L) p L-next // 从第一个数据节点开始 while p ! L // 回到头节点说明遍历完成 print p-data p p-next end while2、双向链表2.1 C 实现下面给出一个 C 实现双向链表创建、插入、删除与遍历的完整示例包含关键步骤注释。#include iostream // 定义双向链表节点结构 struct Node { int data; // 数据域 Node *prev; // 前驱指针指向前一个节点 Node *next; // 后继指针指向下一个节点 Node(int val) : data(val), prev(nullptr), next(nullptr) {} // 构造函数初始化节点 }; // 创建双向链表根据数组元素构建带头节点的双向链表 Node* createList(int arr[], int n) { Node *head new Node(0); // 创建头节点 Node *tail head; // tail 始终指向最后一个节点 for (int i 0; i n; i) { Node *newNode new Node(arr[i]); // 为新元素分配节点 newNode-prev tail; // 新节点的前驱指向当前尾节点 tail-next newNode; // 当前尾节点的后继指向新节点 tail newNode; // 更新尾节点 } return head; } // 在指定节点 p 之后插入新节点值为 val void insertAfter(Node *p, int val) { Node *newNode new Node(val); // 创建新节点 newNode-next p-next; // 新节点的后继指向 p 的后继 if (p-next ! nullptr) { // 若 p 不是尾节点 p-next-prev newNode; // 原后继的前驱改为新节点 } newNode-prev p; // 新节点的前驱指向 p p-next newNode; // p 的后继改为新节点 } // 删除指定节点 pp 不能是头节点 void deleteNode(Node *p) { p-prev-next p-next; // 前驱的后继跳过 p if (p-next ! nullptr) { // 若 p 不是尾节点 p-next-prev p-prev; // 后继的前驱跳过 p } delete p; // 释放 p 的内存 } // 遍历双向链表从头节点的下一个节点开始直到链表结束 void traverseList(Node *head) { Node *p head-next; // 从第一个数据节点开始 while (p ! nullptr) { // 遍历到链表末尾 std::cout p-data ; p p-next; } std::cout std::endl; } int main() { int arr[] {10, 20, 30, 40, 50}; Node *head createList(arr, 5); // 创建双向链表 traverseList(head); // 遍历并输出10 20 30 40 50 insertAfter(head-next, 15); // 在第一个节点后插入 15 traverseList(head); // 输出10 15 20 30 40 50 deleteNode(head-next-next); // 删除值为 20 的节点 traverseList(head); // 输出10 15 30 40 50 return 0; }2.2 408 伪代码考研 408 数据结构中双向链表的创建、插入、删除与遍历通常以伪代码形式考查重点在于理解前驱和后继指针的同步修改顺序。下面给出符合 408 风格的伪代码版本。// 双向链表创建带头节点 // 输入数组 A[1..n]n 为元素个数 // 输出带头节点的双向链表 L CreateList(L, A, n) L new Node // 创建头节点 tail L // tail 指向尾节点 for i 1 to n p new Node // 为新元素分配节点 p-data A[i] // 写入数据 p-prev tail // 新节点的前驱指向当前尾节点 tail-next p // 当前尾节点的后继指向新节点 tail p // 更新尾节点 end for return L // 在节点 p 之后插入值为 val 的新节点 InsertAfter(p, val) s new Node // 创建新节点 s-data val // 写入数据 s-next p-next // 新节点的后继指向 p 的后继 if p-next ! NULL // 若 p 不是尾节点 p-next-prev s // 原后继的前驱改为新节点 end if s-prev p // 新节点的前驱指向 p p-next s // p 的后继改为新节点 // 删除节点 pp 不能是头节点 DeleteNode(p) p-prev-next p-next // 前驱的后继跳过 p if p-next ! NULL // 若 p 不是尾节点 p-next-prev p-prev // 后继的前驱跳过 p end if free(p) // 释放 p 的内存 // 双向链表遍历 // 输入带头节点的双向链表 L // 输出依次输出各数据节点的值 TraverseList(L) p L-next // 从第一个数据节点开始 while p ! NULL // 遍历到链表末尾 print p-data p p-next end while下面从插入、删除、遍历和空间开销四个维度对比双向链表与单链表便于理解两者的差异与适用场景。对比维度双向链表单链表插入已知节点 p 时可在 p 之前或之后插入时间复杂度均为 O(1)但需同步修改前驱和后继指针。已知节点 p 时只能在 p 之后插入时间复杂度 O(1)若要在 p 之前插入需从头遍历找到 p 的前驱时间复杂度 O(n)。删除已知节点 p 时可直接通过 p 的前驱和后继指针完成删除时间复杂度 O(1)无需查找前驱。已知节点 p 时需从头遍历找到 p 的前驱才能完成删除时间复杂度 O(n)若只删除 p 的后继则时间复杂度 O(1)。遍历支持双向遍历既可从前往后也可从后往前适合需要反向访问的场景。仅支持单向遍历只能从前往后访问无法反向回溯。空间开销每个节点额外存储一个前驱指针空间开销更大约为单链表的 1.5 倍。每个节点只存储一个后继指针空间开销更小内存利用率更高。适用场景总结单链表结构简单、空间开销小适合以顺序访问为主、插入删除多发生在表尾或已知节点之后的场景如栈、队列的链式实现。双向链表以额外空间换取操作灵活性适合需要频繁在已知节点前后插入删除、或需要双向遍历的场景如 LRU 缓存淘汰、浏览器前进后退、文本编辑器光标移动等。3、双循环链表3.1 C 实现下面给出一个 C 实现双循环链表创建、插入、删除与遍历的完整示例包含关键步骤注释。双循环链表同时具备双向链表和循环链表的特性既可以从任意节点出发循环访问全部元素又支持双向遍历。#include iostream // 定义双循环链表节点结构 struct Node { int data; // 数据域 Node *prev; // 前驱指针指向前一个节点 Node *next; // 后继指针指向下一个节点 Node(int val) : data(val), prev(nullptr), next(nullptr) {} // 构造函数初始化节点 }; // 创建双循环链表根据数组元素构建带头节点的双循环链表 Node* createList(int arr[], int n) { Node *head new Node(0); // 创建头节点 head-next head; // 头节点的后继先指向自身形成空循环 head-prev head; // 头节点的前驱也指向自身保持双向循环 Node *tail head; // tail 始终指向最后一个节点 for (int i 0; i n; i) { Node *newNode new Node(arr[i]); // 为新元素分配节点 newNode-prev tail; // 新节点的前驱指向当前尾节点 newNode-next head; // 新节点的后继指向头节点保持循环 tail-next newNode; // 当前尾节点的后继指向新节点 head-prev newNode; // 头节点的前驱指向新节点保持双向循环 tail newNode; // 更新尾节点 } return head; } // 在指定节点 p 之后插入新节点值为 val void insertAfter(Node *p, int val) { Node *newNode new Node(val); // 创建新节点 newNode-next p-next; // 新节点的后继指向 p 的后继 newNode-prev p; // 新节点的前驱指向 p p-next-prev newNode; // 原后继的前驱改为新节点 p-next newNode; // p 的后继改为新节点 } // 删除指定节点 pp 不能是头节点 void deleteNode(Node *p) { p-prev-next p-next; // 前驱的后继跳过 p p-next-prev p-prev; // 后继的前驱跳过 p delete p; // 释放 p 的内存 } // 正向遍历双循环链表从头节点的下一个节点开始直到回到头节点 void traverseList(Node *head) { Node *p head-next; // 从第一个数据节点开始 while (p ! head) { // 回到头节点说明遍历完成 std::cout p-data ; p p-next; } std::cout std::endl; } // 反向遍历双循环链表从头节点的前一个节点开始直到回到头节点 void traverseReverse(Node *head) { Node *p head-prev; // 从最后一个数据节点开始 while (p ! head) { // 回到头节点说明遍历完成 std::cout p-data ; p p-prev; } std::cout std::endl; } int main() { int arr[] {10, 20, 30, 40, 50}; Node *head createList(arr, 5); // 创建双循环链表 traverseList(head); // 正向遍历并输出10 20 30 40 50 traverseReverse(head); // 反向遍历并输出50 40 30 20 10 insertAfter(head-next, 15); // 在第一个节点后插入 15 traverseList(head); // 输出10 15 20 30 40 50 deleteNode(head-next-next); // 删除值为 20 的节点 traverseList(head); // 输出10 15 30 40 50 return 0; }3.2 408 伪代码考研 408 数据结构中双循环链表的创建、插入、删除与遍历通常以伪代码形式考查重点在于理解前驱和后继指针的同步修改顺序以及循环终止条件的判断。下面给出符合 408 风格的伪代码版本。// 双循环链表创建带头节点 // 输入数组 A[1..n]n 为元素个数 // 输出带头节点的双循环链表 L CreateList(L, A, n) L new Node // 创建头节点 L-next L // 头节点的后继指向自身形成空循环 L-prev L // 头节点的前驱指向自身保持双向循环 tail L // tail 指向尾节点 for i 1 to n p new Node // 为新元素分配节点 p-data A[i] // 写入数据 p-prev tail // 新节点的前驱指向当前尾节点 p-next L // 新节点的后继指向头节点保持循环 tail-next p // 当前尾节点的后继指向新节点 L-prev p // 头节点的前驱指向新节点保持双向循环 tail p // 更新尾节点 end for return L // 在节点 p 之后插入值为 val 的新节点 InsertAfter(p, val) s new Node // 创建新节点 s-data val // 写入数据 s-next p-next // 新节点的后继指向 p 的后继 s-prev p // 新节点的前驱指向 p p-next-prev s // 原后继的前驱改为新节点 p-next s // p 的后继改为新节点 // 删除节点 pp 不能是头节点 DeleteNode(p) p-prev-next p-next // 前驱的后继跳过 p p-next-prev p-prev // 后继的前驱跳过 p free(p) // 释放 p 的内存 // 双循环链表正向遍历 // 输入带头节点的双循环链表 L // 输出依次正向输出各数据节点的值 TraverseList(L) p L-next // 从第一个数据节点开始 while p ! L // 回到头节点说明遍历完成 print p-data p p-next end while // 双循环链表反向遍历 // 输入带头节点的双循环链表 L // 输出依次反向输出各数据节点的值 TraverseReverse(L) p L-prev // 从最后一个数据节点开始 while p ! L // 回到头节点说明遍历完成 print p-data p p-prev end while双循环链表结合了循环链表与双向链表的优点既可以从任意节点出发循环访问全部元素又支持双向遍历。其插入和删除操作在已知节点位置时时间复杂度均为 O(1)但每个节点需要额外存储前驱和后继两个指针空间开销相对较大。在考研 408 中双循环链表常作为循环链表和双向链表的综合考点出现。4、线性表合并下面给出一个 C 实现两个有序线性表合并的完整示例包含关键步骤注释。合并的核心思路是双指针依次比较两个表的当前元素将较小者放入结果表直到其中一个表遍历完毕再把剩余元素全部追加到结果表末尾。#include iostream #include vector // 合并两个有序线性表升序 // 输入有序数组 a长度 m、有序数组 b长度 n // 输出合并后的有序数组 result std::vectorint mergeSorted(const int a[], int m, const int b[], int n) { std::vectorint result; // 结果表容量为 m n result.reserve(m n); int i 0, j 0; // i 指向 a 的当前元素j 指向 b 的当前元素 // 双指针依次比较将较小者放入结果表 while (i m j n) { if (a[i] b[j]) { result.push_back(a[i]); // a 的当前元素更小放入结果表 i; // 移动 a 的指针 } else { result.push_back(b[j]); // b 的当前元素更小放入结果表 j; // 移动 b 的指针 } } // 若 a 还有剩余元素全部追加到结果表末尾 while (i m) { result.push_back(a[i]); i; } // 若 b 还有剩余元素全部追加到结果表末尾 while (j n) { result.push_back(b[j]); j; } return result; } int main() { int a[] {1, 3, 5, 7, 9}; // 第一个有序线性表 int b[] {2, 4, 6, 8, 10}; // 第二个有序线性表 std::vectorint result mergeSorted(a, 5, b, 5); // 合并两个有序表 std::cout 合并后的有序线性表; for (int x : result) { std::cout x ; } std::cout std::endl; return 0; }运行结果示例合并后的有序线性表1 2 3 4 5 6 7 8 9 10该算法的时间复杂度为 O(m n)空间复杂度为 O(m n)其中 m 和 n 分别是两个有序表的长度。合并过程只需一趟扫描即可完成是考研 408 中线性表合并的常考考点。