企业官网建设流程全解析

1. 线性表到底是什么：先破除"线性表等于数组"的误解

讲到数据结构，十个教程里有九个会把线性表放在第一章。这个安排一点不奇怪，因为后面你要学的栈、队列、字符串、数组，本质上都是线性表的特殊形态。但"线性表"这个概念本身，恰恰是很多人第一个糊里糊涂过去的坎。

我见过不少同学，学完这一章之后留下的印象就是"线性表等于数组"，顶多再加个链表。这个理解不能说全错，但把问题想窄了。线性表（Linear List）的定义其实很朴素：它是n个数据元素组成的有限序列。注意两个关键词：有限，意思是元素的个数是确定的、可数的；序列，意思是元素之间有先后次序，第一个元素没有前驱，最后一个元素没有后继，中间每个元素有且只有一个直接前驱和一个直接后继。

这个"一对一"的逻辑结构，才是线性表的本质。至于底层用数组存还是用链表存，那是存储结构层面的选择，跟逻辑结构是两码事。搞不清楚"逻辑结构"和"存储结构"这两个层次，后面学树、学图的时候一定会更痛苦。树是"一对多"，图是"多对多"，它们的底层照样可以用数组来表示（比如二叉树的顺序存储），但你不会因此说"树就是数组"。

1.1 从生活里找线性表的影子

理解一个抽象概念最有效的方式，是找现实中的映射。线性表在我们的生活中到处都是：

• 排队买奶茶的队伍：每个人都知道自己前面是谁、后面是谁，队头队尾固定，新来的人站到队尾，有人离开就整体往前挪一步——这就是最标准的线性表。
• 手机通讯录：一个联系人的记录有先后顺序，可以按位置（第几条记录）访问，也可以按名字查找，支持中间插入和删除——线性表的基本操作齐了。
• Excel里的一列数据：从上到下的每一格就是线性表的一个元素。

这些例子的共同点是：元素之间有明确的次序关系，操作无外乎"取某个位置的元素、在某个位置插一个、把某个位置的元素删掉、数一数有多少个"。算法设计里的"表抽象数据类型（ADT List）"就是把这几个操作高度归纳之后的结果。

提示：学数据结构的时候，一定要养成"先画图再做代码"的习惯。哪怕是一张非常潦草的方框箭头图，都比直接上代码更接近数据结构的本质。

1.2 线性表的ADT定义为什么要理解

很多学校用的是严蔚敏老师的《数据结构（C语言版）》，教材第二章开头就是一长串ADT定义。坦率讲，那一段是全书劝退率最高的一页，因为看起来全是抽象的名词，不知道背来干嘛。

我的建议是：ADT定义不需要死背，但你必须理解它为什么要这样写。它本质上是一份"接口合同"，规定了线性表对外提供哪些操作：InitList（初始化）、ListEmpty（判空）、Length（求长度）、GetElem（按位取值）、LocateElem（按值查找）、ListInsert（插入）、ListDelete（删除）、PrintList（遍历输出）。这几个操作覆盖了99%的实际使用场景。

理解ADT的另一个价值在于：它是实现无关的。你用顺序表实现这些操作是一种写法，用链表实现又是一种写法，但调用方的代码可以完全一样。这就是抽象的意义——它把"怎么存"和"怎么用"解耦了。举个工程例子，Java里List接口有ArrayList和LinkedList两个实现，换成面向接口编程，业务代码几乎不用改，这就是数据结构层面的抽象能力在工程里的直接体现。

1.3 顺序存储和链式存储：同一逻辑结构的两种"肉身"

线性表有两种最基础的存储结构：

• 顺序存储（顺序表）：用一段地址连续的存储单元依次存放数据元素。你可以直接把它理解成数组，元素在内存里一个挨着一个。
• 链式存储（链表）：用一组地址任意的存储单元存放数据元素，节点之间通过指针串起来。每个节点除了数据，还要额外存一个指针（单链表存一个后继指针，双向链表存两个）。

这两种方案的核心矛盾，就是**"连续"和"非连续"的对立**。顺序表强在随机访问，弱在插入删除要挪动大量元素；链表正好反过来，插入删除只需改指针，但想访问第k个元素得从头一格一格走。这个矛盾会贯穿整篇文章，后面我会详细展开。

2. 顺序表：最直观的存储方案，坑却藏在不显眼的地方

顺序表的核心思路很简单：声明一块连续内存，把元素按次序放进去，再用一个变量记录当前有多少个元素。这一节我会把初始化、查找、插入、删除、扩容全部过一遍，重点说清楚每一段代码背后的"为什么"。

2.1 顺序表的实现骨架（C语言版）

以严蔚敏教材的风格为例，顺序表常用如下定义：

#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 存储元素的数组 int length; // 当前表长 } SeqList;

注意，MAX_SIZE是数组的容量（capacity），length是实际元素个数。这两个概念一定要分开，因为后面不管是动态扩容还是判断满表，全依赖它们。很多新手把length和数组下标混起来，写插入的时候边界判断满天飞，其实只要想清楚一个点：元素从下标0存到length-1，length随时指向"下一个空闲位置"。

初始化、判空、求长度：

void InitList(SeqList *L) { L->length = 0; } int ListEmpty(SeqList L) { return L.length == 0; } int ListLength(SeqList L) { return L.length; }

这几个函数看着简单，但价值在于"约束一致"。你规定好了length == 0表示空表、data才是元素区，那么所有后续操作都围绕这个约定来写，代码就不会乱。

2.2 按位查找：为什么顺序表能O(1)随机访问

int GetElem(SeqList L, int i, int *e) { if (i < 1 || i > L.length) return 0; // 位置非法 *e = L.data[i - 1]; // 第i个元素存在下标i-1 return 1; }

这里有个"位序"和"下标"的经典换算：逻辑位序从1开始，物理下标从0开始。所以第i个元素的存储地址 = 首地址 + (i-1) × sizeof(元素类型)。这个公式意味着什么？意味着不需要遍历，直接用下标做一次偏移就能拿到任意位置的元素——这就是所谓的随机存取（Random Access）。这正是顺序表最值钱的特性，也是后面链表做不到的对照基准。

C语言里L.data[i-1]这句话，编译器算地址的过程就是上面那个公式的体现。你访问L.data[99]和访问L.data[0]，耗时一模一样，跟位置无关。理解了这个，后面学数组和矩阵压缩存储的时候也会轻松很多。

2.3 插入和删除：移动元素才是真正的代价

插入操作逻辑上不复杂：先判断位置合法性和表是否已满，然后把从插入位置开始的元素整体后移一位，最后放入新元素，length加1。

int ListInsert(SeqList *L, int i, int e) { if (L->length >= MAX_SIZE) return 0; // 表满 if (i < 1 || i > L->length + 1) return 0; // 位置非法 for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j - 1]; // 从后往前逐个后移 } L->data[i - 1] = e; L->length++; return 1; }

删除操作与之对称：

int ListDelete(SeqList *L, int i, int *e) { if (i < 1 || i > L->length) return 0; *e = L->data[i - 1]; for (int j = i - 1; j < L->length - 1; j++) { L->data[j] = L->data[j + 1]; // 从前往后逐个前移 } L->length--; return 1; }

这两段代码的核心动作都是元素的批量搬移。插入时从后往前搬，删除时从前往后搬，方向千万别搞反——插到第1个位置，需要把第1个到最后一个全部后移，所以必须先把最后一个挪到后面的空位，再依次往前；如果从前往后搬，前一个元素把后一个覆盖了，数据就丢了。

时间复杂度的计算是这样的：在长度为n的表里，插入位置i（1 ≤ i ≤ n+1）有n+1种选择，每种选择需要移动n-i+1个元素，平均移动次数为：

平均移动次数 = (1/(n+1)) × Σ(i=1 到 n+1) (n-i+1) = (1/(n+1)) × (n + (n-1) + ... + 1 + 0) = n/2

所以在表长n的线性表中插入一个元素，平均需要移动大约n/2个元素，时间复杂度是O(n)。注意这个结论是"平均"意义上的——往表尾插入只需要移动0个元素（O(1)），往表头插入要移动n个（O(n)）。要是你的应用恰好总是往表尾追加，顺序表的真实表现会比O(n)好看得多，这一点到选型部分我会专门展开。

2.4 动态扩容：ArrayList扩容策略为什么是1.5倍

静态数组写起来简单，但MAX_SIZE定死了，装不下更多元素就只能失败。实际工程里更常用的是动态扩容的版本——比如C++的vector、Java的ArrayList、Python的list，本质上都是"会自动长大的顺序表"。

扩容的策略有意思。Java的ArrayList默认容量10，扩容时按1.5倍增长；C++的vector没有统一的扩容倍数，但很多实现是2倍。为什么不每次只加一个位置？因为扩容要做两件事：申请一块更大的连续内存，然后把旧数据全部拷贝过去。假设每次扩容增加1个元素，那么插入n个元素的时间是1+2+3+...+n = O(n²)；而按倍数扩容，log₂n次扩容总共拷贝的元素数量是1+2+4+...+2^k ≈ 2^(k+1) = O(n)量级，均摊到每次插入是O(1)。

注意：**均摊复杂度（amortized analysis）**这个概念在算法分析里很重要。动态数组的push_back操作，绝大部分时候直接写入O(1)，偶尔触发扩容O(n)，但把n次操作的总时间摊到每次，依然是常数级别。王道考研教材里经常考这个点，理解后比死记结论靠谱得多。

为什么用1.5倍而不是2倍？一个常见的解释是：翻倍扩容后，之前释放的旧内存恰好小于新分配的内存，可能无法被下一次扩容复用；而1.5倍配合某些内存分配策略，能提高内存复用率。另一个原因是1.5倍更节省空间，极端情况下2倍扩容可能浪费一半容量。这些属于实现细节，不同语言有不同取舍，但你应该理解的核心是：线性扩容不可取，指数扩容配合均摊分析才是工程正解。

3. 单链表：指针操作是门手艺，别靠背代码

顺序表再好，也有它的天花板——连续内存的"整块"要求，决定了它在需要频繁插入删除、或者元素个数动态变化很大的场景里不好用。链表就是为打破这个约束而生的。

3.1 单链表的结构与初始化

单链表的基本单位是节点（Node），每个节点包含两个部分：数据域（存数据）和指针域（存下一个节点的地址）。在C语言里通常这样定义：

typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域，指向下一个节点 } LNode, *LinkList;

注意struct LNode *next里面为什么写struct LNode而不是LNode——因为typedef还没有执行完，在struct内部只能用完整的类型名struct LNode来声明指针。这是C语言里一个很经典的自我引用写法，面试偶尔会问到。

初始化带头节点的链表：

int InitList(LinkList *L) { *L = (LNode *)malloc(sizeof(LNode)); // 申请头节点 if (*L == NULL) return 0; // 内存分配失败 (*L)->next = NULL; return 1; }

这一步的细节值得抠一下：为什么InitList的参数是LinkList *L而不是LinkList L？因为LinkList本质上是指针类型（LNode *的别名），在函数内部要给这个指针本身赋值（指向新申请的头节点），就必须传指针的地址，也就是LNode **。这是C语言里"想在函数里修改指针变量本身"的标准姿势。很多新手在这上面栽跟头：函数里malloc了，出来发现链表还是NULL，就是因为传进去的是指针的副本。

3.2 头节点 vs 头指针：一个细节，考倒一堆人

这是个经典考点，严蔚敏教材和王道考研书里都反复强调。头指针是指向链表中第一个节点的指针，它标识了整个链表，是链表的"门面"。头节点则是为了操作方便，在第一个元素节点之前额外附加的一个节点，它的数据域一般不存东西（或存链表长度等附加信息），指针域指向第一个元素节点。

头节点的价值在于统一空表和非空表的操作逻辑。假设没有头节点，链表为空时头指针直接是NULL，插入第一个元素时要让头指针指向新节点；链表非空时插入是在某个节点后面接一个节点——两套逻辑，代码里就得写if分支。而有了头节点，空表时头节点的next指向NULL，非空时也还是头节点的next指向某节点，插入和删除一律从头节点开始处理，无需特殊判断。这个"用哨兵节点消除边界分支"的思路，在后续很多数据结构实现里都会复用，比如链式队列的dummy头、红黑树里的nil哨兵节点，其实都是同一招。

实战建议：现在面试手撕链表题，用C/C++时我一般都会先定义dummy node作为头节点，这一招能显著减少边界条件的bug。LeetCode上很多链表题的题解里，ListNode *dummy = new ListNode(0); dummy->next = head;几乎是标配，就是头节点思想在刷题领域的体现。

3.3 链表的插入与删除：先画图，再写码

单链表的插入分为两种情况：在节点p之后插入节点s（已知p的指针），以及在指定位置i插入。

第一种情况最简单：

s->next = p->next; // 先把s接到p原来指向的后继上 p->next = s; // 再把p的指针改为指向s

这两行代码的顺序是铁律：必须先接后继，再改前驱的指针。如果反过来，先执行p->next = s，那么p原来的后继节点就找不到了，链表从这里断掉，后面的节点全丢了。口诀是"先连后断"。

第二种情况，即给定位置i插入，需要先通过遍历找到第i-1个节点，再执行上面的两步操作：

int ListInsert(LinkList L, int i, int e) { LNode *p = L; int j = 0; while (p != NULL && j < i - 1) { // 找到第i-1个节点 p = p->next; j++; } if (p == NULL) return 0; // 位置非法 LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return 1; }

这里的时间开销大头在遍历查找上，平均要找n/2个节点，所以总复杂度是O(n)。但请注意"平均"两个字。如果插入点已知（比如已经拿着指向某个节点的指针），插入本身只需要O(1)，这也是"链表插入比顺序表快"这句话的适用前提——它必须建立在你已经定位到了目标位置附近这个条件上。

删除操作同样分两步：找到目标节点的前驱p，然后q = p->next; p->next = q->next; free(q);。有个变体技巧值得一提：如果要删除的是已知节点p（且不想额外遍历找前驱），可以把p的后继节点的值拷贝到p，然后删掉p的后继节点，这样也做到了O(1)删除——前提是p不是尾节点。这个技巧在LeetCode"Delete Node in a Linked List"里就是标准解法，思路相当精妙。

3.4 头插法、尾插法、前插法：建链表的三种姿势

建链表有两种基本方法。头插法是从头节点开始，每次把新节点插到头节点之后，这样建出来的链表，元素顺序和输入顺序相反；尾插法则维护一个尾指针r，新节点总是接到链表末尾，顺序与输入一致。

// 头插法：结果逆序 LinkList CreateListHead(int arr[], int n) { LinkList L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; for (int i = 0; i < n; i++) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = arr[i]; s->next = L->next; L->next = s; } return L; } // 尾插法：结果正序，需要尾指针 LinkList CreateListTail(int arr[], int n) { LinkList L = (LNode *)malloc(sizeof(LNode)); LNode *r = L; // 尾指针，初始指向头节点 for (int i = 0; i < n; i++) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = arr[i]; r->next = s; r = s; // 尾指针后移 } r->next = NULL; // 别忘了封口 return L; }

头插法虽然建出的链表是逆序的，但在某些场景反而是优势——比如从单链表快速构造反转后的链表。尾插法的关键是尾指针的维护，以及最后一定要r->next = NULL，否则链表末尾会悬空，遍历时造成野指针问题。

前插法是真题里的高频考点，它要求在第i个元素之前插入一个新元素。由于单链表只能向后走，前插的常规做法是：找到第i-1个节点p，在p之后插入——也就是把"前插"转化为"p的后插"，插入位置向前移一位。代码逻辑和后面的ListInsert完全一致，核心是理解这个"前插变后插、位置左移一位"的转化思想。

4. 双向链表和循环链表：什么时候值得多花一份指针空间

单链表有个天生的短板：只能往后走。做删除操作时，我们惊T发现需要知道前驱，但单链表里前驱只能重新遍历——这就是"单向"的代价。解决思路也很直接：每个节点再存一个前驱指针，于是有了双向链表。

4.1 双向链表的节点定义与插入删除

typedef struct DNode { int data; struct DNode *prior; // 前驱指针 struct DNode *next; // 后继指针 } DNode, *DLinkList;

双向链表在任意位置删除节点，理论上可以做到O(1)——因为有了前驱指针，不需要再遍历找前驱。插入操作需要改四个指针，比单链表多了两个，因此改指针的顺序一定要彻底搞清楚，否则很容易出现"指针悬空"或者"节点从链表中丢出去"的bug。

在节点p之后插入节点s：

s->next = p->next; s->prior = p; if (p->next != NULL) { p->next->prior = s; // 这里判断很重要：如果p是尾节点，p->next为NULL } p->next = s;

删除节点p：

p->prior->next = p->next; if (p->next != NULL) { p->next->prior = p->prior; } free(p);

注意插入和删除都涉及对p->next是否为NULL的判断。尾节点后面没有后继，所以它的next是NULL，如果你不判断就直接访问p->next->prior，就是空指针解引用，程序直接崩溃。这类问题在考研选择题里是高频干扰项，实战中调试也是高发区。

代价很清楚：每个节点多了一个指针的内存占用（64位系统下是8字节），而且插入删除时指针操作的数量翻倍，出bug的概率也翻倍。所以工程上要不要用双向链表，关键是看你的操作里"删除已知节点"和"从后往前遍历"是不是真的高频。像Java的LinkedList内部就是双向链表，因为它要支持从两个方向迭代；而Linux内核链表实现里更是把指针域做进了结构体，所有节点通过list_head串起来，那就是另一个层级的话题了。

4.2 循环链表与快慢指针判环

循环链表（circular linked list）把最后一个节点的next指针指向头节点（带上头节点的话），这样就形成了一个环，从任意节点出发都能走回原点。它最直观的应用场景是循环队列和约瑟夫环问题。

判断单链表是否有环是面试高频题。经典的解法是快慢指针（Floyd判圈算法）：fast指针每次走两步，slow指针每次走一步，如果链表有环，两者必然相遇；如果无环，fast会先到NULL。为什么快慢指针一定能相遇？因为每轮迭代fast相对slow推进一个节点，两者的距离逐步缩小，最终会追上。这个证明思路比代码本身更重要，面试官大概率会追问。

int HasCycle(LNode *head) { if (head == NULL || head->next == NULL) return 0; LNode *slow = head->next; LNode *fast = head->next->next; while (fast != NULL && fast->next != NULL) { if (slow == fast) return 1; slow = slow->next; fast = fast->next->next; } return 0; }

4.3 约瑟夫环问题：循环链表最经典的实战

约瑟夫环问题描述起来很简洁：n个人围成一圈，从第1个人开始报数，报到m的人出列，然后从下一个人重新报数，直到所有人出列，求出列顺序。这个题的经典解法就是循环链表：

void Josephus(int n, int m) { DLinkList head = NULL, p = NULL, q = NULL; // 建一个循环双向链表，节点数n，编号1~n（构建代码略） p = head; while (p->next != p) { // 当只剩一个节点时停止 for (int i = 1; i < m; i++) { p = p->next; // 报数相当于指针移动m-1次 } printf("%d ", p->data); // 当前p出列 q = p->next; p->prior->next = p->next; p->next->prior = p->prior; free(p); p = q; // 从下一个节点继续 } printf("%d\n", p->data); }

这里用双向循环链表比较顺手，删除任意节点只需要O(1)，报数移动指针的复杂度是O(m)，总共n次，整体O(n·m)。如果数据规模大，有更聪明的数学解法（约瑟夫环的递推公式），不过那属于"数学层面优化"的范畴，数据结构课程里能用循环链表把它跑通，就已经达标了。

5. 选型不靠口诀：顺序表和链表的真实差距比你想的大

我见过很多人背一句"频繁插入删除用链表，频繁查询用顺序表"就去应付考试和面试了。这句话理论上没错，但它掩盖了一个非常重要的工程事实：同样的O(n)复杂度，常数因子可能差出一个数量级。而在当代计算机的内存架构下，顺序表在很多场景甚至比链表更"快"——即便它需要搬移元素。

5.1 复杂度之外的两个隐藏维度

第一个隐藏维度是CPU缓存命中率。顺序表的元素是连续存放的，遍历时CPU会把相邻的内存块预取到缓存里（cache line通常是64字节），一趟遍历下来缓存命中率极高。链表的节点分散在各个malloc分配出来的内存块里，遍历一个节点就要访问一次内存地址，几乎每次都是cache miss。在数据量大到超过CPU缓存的场景（比如几百万个节点），顺序表遍历比链表遍历快10倍以上并不夸张。国外有人专门做过benchmark，结果基本都是"数组完胜"。

第二个隐藏维度是内存分配的开销。链表每创建一个节点就要malloc一次，malloc本身有系统调用和堆管理开销，而且会产生内存碎片；顺序表只在扩容时分配一次内存，摊销下来小得多。如果你在高频插入节点的场景使用链表，malloc的时间很可能会让你怀疑人生。

5.2 理论复杂度的精确对照

把关键操作的时间复杂度（n为表长）列成一张表，会更清楚：

看完这张表你会发现，"插入删除链表快"这句话只有在已知节点指针的前提下才完全成立。如果每次都是从表头开始找位置插入，链表的O(n)可能比顺序表的O(n)还要慢，因为顺序表至少缓存友好，而链表每次都伴随cache miss和malloc。

5.3 实际项目中的选型建议

根据我自己的项目经验，几个实用的选型判断标准：

• 以随机访问为主（按下标取元素、排序、二分查找）：无脑顺序表，数组/vector/ArrayList就是为你准备的。
• 频繁在头部插入删除：顺序表要搬移大量元素，链表头插O(1)，这个场景链表胜。
• 频繁在中间或尾部插入删除：需要结合"是否已持有插入位置指针"判断。如果业务场景每次插入都伴随一次"查找定位"，那两者的理论复杂度差不多，此时优先考虑顺序表，理由是缓存友好和实现简单。
• 元素个数不确定且波动大：动态扩容的顺序表或者直接上链表都行。如果插入的峰值很高，且每个节点数据较小，链表碎片化问题不严重；如果节点数据很大，顺序表扩容的拷贝成本高，可以选链表。

一句话总结：不要背口诀，要背场景。选型的前提永远是"你的实际操作的访问模式是什么"，而不是"哪句话听起来更经典"。

6. 高频题型拆解：从考研真题到面试手撕

线性表这一章是考研408、期末考、以及各大公司面试手撕算法题的重灾区。很多人感觉"课都听懂了，题就是做不出来"，原因是缺少一个"题目模式"的归纳。我按自己的备考和教学经验整理几类高频题型，每一类给出解题套路，这样你刷题时就能"见题识套路"，而不是每次都是现场推。

6.1 链表反转：迭代、递归、头插三兄弟

链表反转是面试出现频率最高的链表题，没有之一。迭代写法最经典，用三个指针prev、curr、next滚动推进：

LNode *ReverseList(LNode *head) { LNode *prev = NULL; LNode *curr = head; while (curr != NULL) { LNode *next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

递归写法非常简洁，但理解门槛也高：先反转后面的链表，再把当前节点接到反转后的链表尾部：

LNode *ReverseListRecursive(LNode *head) { if (head == NULL || head->next == NULL) return head; LNode *newHead = ReverseListRecursive(head->next); head->next->next = head; head->next = NULL; return newHead; }

第三种是头插法反转：新建一个头节点，遍历旧链表，把每个节点头插到新链表里，自然就是逆序。这个思路如果你在建链表时练过头插法，几乎不用思考就能写出来——这也是我把头插法放在前面讲的原因，知识点都是串起来的。

反转的变体还有"反转前k个节点""每k个一组反转""反转区间"，万变不离其宗，核心都是指针的重新连接顺序。我练的时候会在纸上画个五节点的链表，手动走一遍三个指针的变化，画熟之后再难的变体也不慌。

6.2 快慢指针双雄：找中点、找倒数第k个节点

快慢指针不只是用来判环。找链表中间节点可以用"快指针走两步、慢指针走一步"，快指针到链尾时，慢指针正好在中点；找倒数第k个节点则可以用"快指针先走k步，然后快慢指针同步走"，快指针到NULL时，慢指针指向的就是倒数第k个节点。

LNode *FindKthFromEnd(LNode *head, int k) { LNode *fast = head, *slow = head; for (int i = 0; i < k; i++) { if (fast == NULL) return NULL; // k超过链表长度 fast = fast->next; } while (fast != NULL) { fast = fast->next; slow = slow->next; } return slow; }

这类题考的是"用两个指针制造距离差"的思维模型，而不是什么高深的算法。一旦你建立了这个模型，合并两个有序链表、删除倒数第N个节点、判断回文链表这些题目都会迎刃而解。

6.3 合并有序链表与链表排序

合并两个有序链表是归并排序链表版的前置技能，标准写法用递归：

LNode *MergeTwoLists(LNode *l1, LNode *l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->data <= l2->data) { l1->next = MergeTwoLists(l1->next, l2); return l1; } else { l2->next = MergeTwoLists(l1, l2->next); return l2; } }

这里递归的终止条件其实很关键——只要有一个链表走完，直接把另一个剩下的整段接上，省去逐节点遍历。链表排序最常考的是链表插入排序和链表归并排序，两者都不需要额外的大块内存，归并排序的时间复杂度可以稳定在O(n log n)。如果面试遇到"对链表排序"，我一般先写归并排序——快速排序对链表并不友好，因为快排的partition依赖随机访问元素，链表下标访问是O(n)，性能优势发挥不出来。

6.4 实验报告和期末里的"实现+证明"组合题

除了算法题，很多读者可能是为了课程实验报告来的。典型的实验报告题目包括：

• 顺序表的基本操作实现：要求写初始化、插入、删除、查找、打印，并输出每一步的结果。这种报告的重点不是代码多华丽，而是测试用例要覆盖边界——空表插入、满表插入、越界位置插入、删除首尾元素，每一条都要有输出截图和说明。
• 单链表的建立与操作：要求实现头插法/尾插法建表，以及插入删除，并验证头节点的重要性。报告中如果能加一段"带头节点与不带头节点的对比测试"，分数通常会高一截。
• 两个有序表的合并（也就是归并思想的顺序表应用）：要求实现Merge操作并分析时间复杂度。这道题是考"归并思想"的，代码实现不难，重点是把三指针（i、j、k）的推进逻辑讲清楚。

写实验报告的技巧是：不要只贴代码，要把每一步的设计意图写出来。比如"删除时为什么从前往后搬""插入时为什么从后往前搬""为什么用循环双向链表实现约瑟夫环"。很多老师改实验报告，最看重的就是这个"为什么"，而不是那一堆谁都能从网上抄来的代码。

7. 学完这一章，我踩过的坑和你大概率也会踩的坑

最后聊一些"人话"总结。这部分是我自己当年学线性表、以及后来帮别人改代码时反复遇到的高频错误，每一条都对应真实的debug经历，希望你能跳过这些坑。

第一个坑我不止一次说过，就是把逻辑位序和物理下标搞混。教材里的插入删除一律用"第i个元素"来描述，i从1开始；而代码里的数组下标从0开始。写循环的时候顺拐，要么越界要么漏元素，最后打印结果错位。解决方法是写代码前先定好"约定"：注释里写清楚i是逻辑位序（从1开始），代码里所有访问都用i-1转换位序。

第二个坑是malloc之后不检查返回值。虽然在竞赛和刷题环境里malloc失败的概率很低，但在课程设计里内存申请多了照样可能失败。不检查就直接解引用，轻则段错误，重则产生一堆莫名其妙的bug。我建议所有链表相关函数里，malloc之后都要加一句if (s == NULL) return 0;，这不算繁琐，是基本素养。

第三个坑是遍历时修改链表结构。比如在遍历链表的过程中同时删除当前节点，如果你直接用p = p->next来推进，删除后p可能已经指向了被释放的内存，下一轮循环就成了野指针访问。正确的套路是：先取next指针，再做删除操作，最后把p移到next。类似的还有在头插法建链时用原链表的遍历指针做forward，稍不留神就把链表搞断了。

第四个坑是只在初始化时malloc，忘了销毁。C语言写链表不释放内存，程序跑完可能没问题，但课程设计里如果你写了一个多次创建链表的循环，内存泄漏会越来越明显。终结点记得写一个DestroyList，把每个节点free掉，最后把头节点也free了。这不是数据结构的考点，但它是你代码质量的门面。

第五个坑其实算不上坑，是认知层面的：所有教科书都不是让你背的，是让你操作的。线性表这一章的代码，光看懂没有任何用，真正有效的最小练习是：关掉书，自己从零写一个顺序表、一个单链表，动手插删改查，直到循环边界、指针指向、分配释放这些动作变成肌肉记忆。数据结构的"感觉"就是在这个过程里长出来的，谁也替代不了你自己的手。

学数据结构-线性表这一章，就跟学骑自行车一样——看一百个教程不如摔一次跤。理论部分看到这里，你已经把顺序表、链表、双向链表、循环链表以及它们的复杂度都过了一遍，剩下的就是打开编辑器，亲手把顺序表的插入循环写对、把链表反转的指针画明白。等你哪一天能把链表反转不看资料直接写出来，你会发现后面学栈、队列、树、图，都会顺滑很多，因为那时候你已经打通了"存储结构-逻辑结构-操作算法"这条主线。