企业官网建设流程全解析

上个月整理代码仓库，翻出一个命名草率的文件，里面摞着三版链表实现，从“单链表v1”一路改到“/////链表”。不少人问过我同一个问题：都什么年代了，还有必要研究链表？我的答案一直没变——太有必要了。链表不光是面试题里的常客，更是理解指针、内存布局、算法复杂度的最佳训练场。这篇文章打算把手写链表的完整思路摊开讲：从C++结构体链表基本语法，到链表遍历、链表插入、逆置链表，再到循环单链表、嵌入式链表代码示例，最后聊聊基于链表的两个集合差集怎么做。适合正在补数据结构基础、准备面试，或者要在嵌入式环境里手工管理动态内存的读者。内容不绕弯子，全部按可复现代码来。

1. 为什么说链表是“老古董”里最不过时的数据结构

1.1 数组和链表差的不是一星半点

很多人学链表之前已经熟练使用数组，觉得链表不过就是“不能随机访问的数组”，这是一个很大的误解。数组和链表解决的是完全不同的内存组织问题。

数组在内存里是一整块连续空间，声明一个int arr[100]，系统就给你划出400字节连着的位置。访问arr[i]只需要用arr + i * sizeof(int)做一次地址计算，这就是O(1)随机访问的来源。但它的代价也在这里：想在第10个位置插入一个新元素，后面的90个元素全部要往后挪；想删除第10个元素，后面的元素又得往前补。最坏情况下，一次插入要搬动整个数组。

链表则完全不同。它的每个节点都是独立分配的内存，靠指针把彼此“串”起来。节点在物理内存里可以东一个西一个，上一个节点的next指向下一个节点的地址。这样插入和删除只需要修改相邻节点的指针，不需要搬动任何数据。代价是访问某个位置的元素必须从头开始一个一个往后走，随机访问是O(n)。

打个比方：数组像一栋楼里连续编号的房间，靠门牌号直接找；链表像一条铁链子，每节车厢都知道下一节是谁，想找第100节车厢只能从车头一节节数过去。这两种结构没有谁绝对取代谁，而是各自擅长不同场景。链表在处理频繁增删、数据量不可预估的场景下有天然优势，这也是操作系统和嵌入式系统至今大量使用链表的原因。

1.2 真实系统里链表无处不在

链表不是只在教科书和面试题里出现，它在我们每天用的系统里到处都是。

• 操作系统的进程管理：Linux内核里task_struct通过链表把所有进程串起来，新增、退出进程时只需要做指针操作。
• 内存管理：很多系统用空闲链表（free list）记录可分配的内存块，分配和释放时就是链表节点的摘除和挂入。
• LRU缓存：CPU的Cache替换策略、Redis的LRU淘汰算法，核心都是一个双向链表加哈希表。
• 文件系统：目录项缓存、空闲块管理经常用到链表。
• 嵌入式消息队列：中断处理程序和主循环之间传递数据，最常见的数据结构就是循环单链表实现的环形队列。

一句话：链表不是一个“过时的玩具”，而是一种底层的、系统级的组织思想。把链表写熟练，意味着你能理解指针怎么工作、内存怎么布局、边界条件为什么会出事。下面开始动真格的——从零手写一个单链表。

2. 单链表从零实现：C++结构体链表基本语法与插入删除全流程

2.1 节点结构：带头节点和不带头的差别

先定义最基础的节点结构。一个节点保存一个数据域和一个指向下一个节点的指针，在C++里最简单就是结构体：

struct Node { int data; Node* next; };

这个next就是“铁链”上的连接环。创建三个节点并串起来，代码长这样：

Node* head = new Node{1, nullptr}; head->next = new Node{2, nullptr}; head->next->next = new Node{3, nullptr};

这种写法的特点是：head指针直接指向第一个数据节点。好处是代码直观，坏处是涉及删除第一个节点、或者在头部插入节点时，必须修改head指针本身，稍不留神就会丢头。

另一种常见的做法是加一个“头节点”（dummy node）。头节点不存数据，它的next才指向真正的第一个数据节点：

Node* dummy = new Node{0, nullptr}; dummy->next = new Node{1, nullptr};

有头节点的好处在于：无论操作哪个数据节点，都不需要动dummy这个头指针，代码的边界判断会少很多。很多工程的链表实现都会带头节点，比如Linux内核链表的各种操作宏，本质上就是围绕一个固定的头节点转。我自己在实际项目里更推荐带头节点，尤其是新手阶段，能少踩一堆空指针的坑。

2.2 插入操作：头插、尾插、中间插三种场景

插入是链表最核心的操作，理解了插入，差不多就理解了链表一半的指针逻辑。三种插入场景分别说。

头插。新节点成为新的第一个节点，所以要先把新节点的next指向原来的头，再更新head。注意顺序不能反，反了就把原有链表弄丢了：

void insertAtHead(Node*& head, int val) { Node* newNode = new Node{val, nullptr}; newNode->next = head; head = newNode; }

这里有个非常重要的细节：head参数类型是Node*&，也就是指针的引用。如果写成Node* head，函数内部修改head只是改了形参副本，调用结束后原来的head根本不会变——这就是经典的“值传递丢头”问题，后面踩坑章节我会专门展开。

尾插。需要先找到当前链表的最后一个节点，让它的next指向新节点：

void insertAtTail(Node*& head, int val) { Node* newNode = new Node{val, nullptr}; if (head == nullptr) { head = newNode; return; } Node* cur = head; while (cur->next != nullptr) { cur = cur->next; } cur->next = newNode; }

尾插的时间复杂度是O(n)，因为无论如何都要遍历到链表末尾。如果频繁做尾插，工程上会让表头表尾各存一个指针。

中间插。最常用的是在某个已知节点后面插入，这个操作时间复杂度是O(1)，也是链表对比数组最漂亮的地方：

void insertAfter(Node* prev, int val) { if (prev == nullptr) return; Node* newNode = new Node{val, nullptr}; newNode->next = prev->next; prev->next = newNode; }

注意newNode->next = prev->next这一步必须先做，再把prev->next指向新节点。顺序一旦写反，原来的后继节点就找不到了。

2.3 删除操作：最怕丢头丢尾

删除相比插入稍微绕一点。删除的核心问题是：单向链表只知道当前节点的后继，不知道前驱，所以要删除某个节点，必须找到它的前驱节点，让前驱的next跳过被删节点，指向被删节点的下一个节点。

按值删除的完整代码：

void deleteNode(Node*& head, int val) { if (head == nullptr) return; if (head->data == val) { Node* tmp = head; head = head->next; delete tmp; return; } Node* cur = head; while (cur->next != nullptr && cur->next->data != val) { cur = cur->next; } if (cur->next != nullptr) { Node* tmp = cur->next; cur->next = tmp->next; delete tmp; } }

这里有两个边界条件要重点盯：

一是删除的是头节点。这时必须直接更新head，否则头指针会指向一块被释放的内存，后续遍历直接崩溃。

二是空链表和找不到目标值。空链表时cur->next存在的前提是head != nullptr，上面的代码用if (head == nullptr) return;做了保护；找不到目标值时，循环退出条件是cur->next == nullptr，自然什么也不做，不会误删。

一个常见的设计误区是“删除节点时直接把传入的节点指针delete掉完事”。真正工程上要删哪个节点，往往是按值、按下标或者按条件找到的，而找到之后必须是在“前驱节点”层面操作，而不是在当前节点层面。很多新手写delete cur之后继续用cur，这就是悬垂指针的典型来源。

3. 遍历和逆序：把最常见的三个操作吃透

3.1 遍历：一切操作的基础

遍历是链表所有操作的基石，插入要遍历找位置，删除要遍历找前驱，逆置要遍历改指针，打印要遍历输出。单链表的遍历非常简单：

void printList(Node* head) { for (Node* cur = head; cur != nullptr; cur = cur->next) { std::cout << cur->data << " "; } std::cout << std::endl; }

循环的终止条件是cur != nullptr，意思是走到链表最后一个节点的next（也就是nullptr）就停。这个循环里最关键的思维转变是：不要想着“当前位置是第几个”，而要想着“当前指针指向谁，它的next是谁”。链表里没有任何下标概念，所有的操作都是顺着next往下“走”。

遍历时最容易犯的错是循环里更新了cur->next却忘了更新cur本身，或者在循环体内部修改了cur->next，导致跳过了节点。写链表遍历，心里要时刻清楚“cur现在指向哪、cur下一步指向哪”。

3.2 逆置链表的三种写法：头插法、三指针、Python版

逆置链表是链表操作里最经典、也最能检验指针基本功的题目。一个链表1 -> 2 -> 3 -> 4 -> NULL，逆置后要变成4 -> 3 -> 2 -> 1 -> NULL。

头插法逆置。思路很朴素：把原链表从头到尾摘下来，每个节点都往一个新链表的头部插入，最后新链表就是逆序的。

Node* reverseByHeadInsert(Node* head) { Node* newHead = nullptr; Node* cur = head; while (cur != nullptr) { Node* next = cur->next; // 先保存后继，否则断了找不回来 cur->next = newHead; // 当前节点指向新链表头部 newHead = cur; // 新链表头更新为当前节点 cur = next; // 继续处理原链表的下一个节点 } return newHead; }

三指针逆置。思路是在原链表上原地改指针方向，用三个指针prev、cur、next分别记录前驱、当前、后继：

Node* reverseByThreePointers(Node* head) { Node* prev = nullptr; Node* cur = head; while (cur != nullptr) { Node* next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

每次循环做一件事：把cur->next从指向后面的next改成指向前面的prev。改完之后prev和cur整体往后挪一格。循环结束时cur为nullptr，prev停在原链表的最后一个节点，也就是新链表的头。

头插法需要额外的newHead指针，三指针法不需要额外链表，但本质都是“边走边改方向”。我个人建议把三指针法练到闭着眼睛能写，因为它在空间上最省，也是面试时最加分的写法。

Python单链表逆序。Python没有指针语法，但思路完全一致。定义节点类，然后同样用三个游标完成：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

递归版本也值得一提，它能让代码更短，但递归深度受栈限制，长链表下有爆栈风险：

def reverse_recursive(node): if node is None or node.next is None: return node new_head = reverse_recursive(node.next) node.next.next = node node.next = None return new_head

递归的思路是：先假设后续链表已经逆置完成，再把当前节点接到尾部。理解递归逆置的关键是node.next.next = node这行——它让当前节点的后继节点反过来指向当前节点，相当于把箭头掉了个方向。

3.3 写完逆置后如何自测

逆置代码写出来不代表对，一定要自测。我的习惯是测这么几个用例：

• 空链表：输入nullptr，期望返回nullptr。
• 单节点链表：只有一个节点，逆置后还是它自己。
• 两个节点：1 -> 2，逆置后2 -> 1，重点看头指针是否正确。
• 三个及以上的节点：反转后打印，确认首尾正确、中间顺序没乱。

很多bug在三个节点以上的用例里才会暴露，尤其是指针顺序写反时，链表不是变成循环就是丢掉中间节点。如果手边没有调试器，打印遍历是最快的手段。逆置后打印链表，看到4 3 2 1就是对的，看到4或者死循环就是哪里出了问题。

4. 循环单链表实战：约瑟夫问题与环形队列

4.1 循环单链表：尾节点又指回了头节点

循环单链表和普通单链表唯一的区别是：最后一个节点的next不再指向nullptr，而是指向头节点，形成一个环。这个看似微小的变化，带来两个直接影响：

第一，遍历的终止条件从cur != nullptr变成了cur != head。因为环里没有nullptr，不能再用“走到空就停”的方式判断了。

第二，整个链表没有天然的“头”和“尾”，任何节点都可以作为入口开始遍历。这在需要循环轮转的场景下特别自然。

创建循环链表的典型过程是先构建好普通单链表，再把尾节点的next指向头：

Node* head = new Node{1, nullptr}; Node* tail = head; for (int i = 2; i <= 5; i++) { Node* node = new Node{i, nullptr}; tail->next = node; tail = node; } tail->next = head; // 关键一步，形成循环

遍历循环链表要用do...while，确保至少执行一次再判断是否回到起点：

Node* cur = head; do { std::cout << cur->data << " "; cur = cur->next; } while (cur != head);

4.2 约瑟夫问题：循环链表的经典应用

约瑟夫问题是个流传很广的故事：n个人围成一圈，从第一个人开始报数，报到m的人出列，然后下一个人重新从1开始报数，直到只剩最后一个人，求最后幸存者的编号。

这个问题几乎所有讲循环链表的地方都会提到，原因很简单，它天然就是一个“围成一圈不断数数”的问题。用循环单链表实现非常直观：

int josephus(int n, int m) { Node* head = nullptr; Node* tail = nullptr; for (int i = 1; i <= n; i++) { Node* node = new Node{i, nullptr}; if (head == nullptr) { head = node; tail = node; } else { tail->next = node; tail = node; } } tail->next = head; Node* cur = head; Node* prev = tail; int count = 1; while (prev != cur) { if (count == m) { Node* tmp = cur; prev->next = cur->next; cur = cur->next; delete tmp; count = 1; } else { prev = cur; cur = cur->next; count++; } } return cur->data; }

核心逻辑就一句话：数到m就把当前节点从环里摘掉。摘的时候要借助prev记录前驱，因为单链表无法回头找前驱。循环终止条件是prev != cur，意思是当前还剩下最后一个节点时，它自己指向自己，就该停下来了。

这个实现里我特别想强调一个细节：删除节点后，cur直接移到prev->next，也就是被删节点的后继。这样下一个报数的人正好是原链表里被删节点的下一位，符合“下一个人重新从1开始报数”的规则。

4.3 循环单链表在嵌入式消息队列中的应用

抛开面试题，循环单链表在嵌入式领域有个非常实际的应用——环形缓冲区。

单片机或者RTOS环境下，中断服务程序往里写数据，主循环里往外取数据，这中间需要一个缓冲区。如果直接用数组，要额外维护读写索引、处理索引回绕；用循环单链表，天然就是一个环形结构，写的一端只需要往尾节点后面追加，或者干脆固定一个“写指针”在环上不断前进，读的一端跟着“读指针”追。这比数组实现更灵动，也比线性链表实现更省心——不用担心队列空了还往外取、队列满了还往里写导致指针越界。

我见过不少嵌入式项目里，消息队列就是用固定大小的循环链表加两个游标实现的。固定大小的原因后面章节会讲，嵌入式环境不能随便malloc，节点要么静态分配，要么从内存池里取。

5. 嵌入式环境下的链表：从内存布局到代码示例

5.1 嵌入式环境的内存约束，直接决定链表的写法

嵌入式环境写链表和PC上写链表有个很大的区别：内存既小又碎。

PC上可以放心地new、delete，操作系统帮忙管理堆，偶尔碎个片也没什么感觉。嵌入式环境里，RAM可能只有几十KB，堆很小甚至根本没有，频繁动态分配内存会导致内存碎片，时间长了碎片多到连小块内存都分配不出来。更要命的是，如果中断和主循环同时访问链表，不加保护还会出现数据竞争。

所以嵌入式链表代码示例，跟我上面写的PC版有个根本差异：节点内存不动态分配，而是用静态数组或者内存池。这样地址固定、分配时间确定、不会碎片化，中途中断不会因为分配内存引入不确定性。

5.2 静态内存池里的链表代码示例

一个简单的思路是：预先定义一个节点池数组，再用一个空闲链表来管理哪些节点可用。节点被使用时挂到业务链表上，释放时归还到空闲链表。

#define POOL_SIZE 32 typedef struct Node { int data; struct Node* next; } Node; static Node pool[POOL_SIZE]; // 节点池 static Node* freeList; // 空闲链表的头 void poolInit(void) { freeList = &pool[0]; for (int i = 0; i < POOL_SIZE - 1; i++) { pool[i].next = &pool[i + 1]; } pool[POOL_SIZE - 1].next = NULL; } Node* allocNode(int data) { if (freeList == NULL) return NULL; // 池已耗尽 Node* node = freeList; freeList = freeList->next; node->data = data; node->next = NULL; return node; } void freeNode(Node* node) { node->next = freeList; freeList = node; }

有了这个池子，业务代码里创建和销毁节点的时间都是固定的，不会被堆管理器的复杂逻辑拖慢。这个模式我在多个MCU项目里实测过，稳定可靠。

另外嵌入式里还有一种更彻底的“侵入式链表”，代表性就是Linux内核的list_head结构。它的特点是节点自己不存数据，而是挂在宿主结构体里，通过指针找到宿主。好处是一个链表操作代码可以被所有业务复用，坏处是理解门槛高一些。对大多数嵌入式项目来说，简单直白的节点池方案已经够用。

5.3 中断环境下的链表操作，三个必须注意的点

嵌入式链表真正容易出问题的地方，在于中断和主循环共享链表。

第一，访问必须互斥。主循环在用链表时来了中断，中断里也操作同一个链表，两个执行流同时改指针，链表很快就断成几截。最简单有效的方法是：中断里只做标记，链表操作全部放到主循环里做；如果必须在中断里操作，就用关闭中断或者临界区保护。

第二，释放节点的时机要小心。中断里释放一个节点到空闲链表，主循环正在用的却是另一个链表，两个链表互相独立还好，如果共用一个空闲池，就要保证分配和释放都是原子的。

第三，不要在主循环里长时间占用临界区。链表操作本身很快，但遍历一个长链表就不快了。关中段时间太长，中断延迟就会超标。实际做法往往是中断只把数据往环形队列里塞，主循环批量处理，处理完之后统一归还节点。

6. 基于链表的两个集合的差集：一个完整算法拆解

6.1 集合差集的含义和链表存储的特点

集合A和集合B的差集记作A - B，意思是“属于A但不属于B”的元素。比如A是{1, 2, 3, 5}，B是{2, 4, 5}，那么A - B就是{1, 3}。

当这两个集合分别用链表存储时，问题就变成了在一个链表上做关系运算。先别急着写双层循环，想清楚链表和集合各自的约束条件：

• 链表没有下标，不能O(1)随机访问，所以依赖随机访问的算法要重新考虑。
• 集合要求元素不重复，所以结果链表里不能出现重复值，除非输入本身保证无重复，否则要先处理去重。
• 差集不改变原有集合，所以不能破坏A、B两个链表本身，要么原地操作创造条件，要么新开一个链表存结果。

6.2 朴素解法：双重遍历加标记

最容易想到的方法是：遍历A中每个元素，再到B里完整找一遍，找到就不加入结果，找不到就加入结果。

Node* setDifferenceNaive(Node* A, Node* B) { Node* dummy = new Node{0, nullptr}; Node* tail = dummy; for (Node* pa = A; pa != nullptr; pa = pa->next) { bool found = false; for (Node* pb = B; pb != nullptr; pb = pb->next) { if (pa->data == pb->data) { found = true; break; } } if (!found) { tail->next = new Node{pa->data, nullptr}; tail = tail->next; } } return dummy->next; }

时间复杂度是O(nm)，A有n个元素、B有m个元素时，最坏要做nm次比较。这个方法代码直白，不依赖任何额外空间，适合两个链表都很小的场景。但如果A有十万个节点，B也有十万个，这个算法就跑不动了，必须优化。

如果B的元素范围很小时，还可以用标记数组替代第二层循环——开一个足够大的布尔数组，先遍历B把存在的值标记，再遍历A查标记。代价是需要一块和取值范围等大的额外内存。这个方案适合值域紧凑的场景，比如数值都是0到10000以内的整数时非常香。

6.3 排序加双指针：把差集复杂度降下来

更通用的优化是排序加双指针。先把A、B两个链表各自排成升序，然后同时从头扫描，比较过程中两个指针各走各的：

Node* sortedInsert(Node* head, int val) { Node* node = new Node{val, nullptr}; if (head == nullptr || head->data >= val) { node->next = head; return node; } Node* cur = head; while (cur->next != nullptr && cur->next->data < val) { cur = cur->next; } node->next = cur->next; cur->next = node; return head; } Node* setDifferenceSorted(Node* A, Node* B) { Node* sortedA = nullptr; for (Node* p = A; p != nullptr; p = p->next) { sortedA = sortedInsert(sortedA, p->data); } Node* sortedB = nullptr; for (Node* p = B; p != nullptr; p = p->next) { sortedB = sortedInsert(sortedB, p->data); } Node* dummy = new Node{0, nullptr}; Node* tail = dummy; while (sortedA != nullptr && sortedB != nullptr) { if (sortedA->data < sortedB->data) { tail->next = new Node{sortedA->data, nullptr}; tail = tail->next; sortedA = sortedA->next; } else if (sortedA->data > sortedB->data) { sortedB = sortedB->next; } else { sortedA = sortedA->next; sortedB = sortedB->next; } } while (sortedA != nullptr) { tail->next = new Node{sortedA->data, nullptr}; tail = tail->next; sortedA = sortedA->next; } return dummy->next; }

双指针比较的逻辑不复杂：sortedA的值小，说明它不可能在B里出现（B已经是升序，后面的值只会更大），直接收进结果；sortedB的值小，说明A当前的值可能在B后面，把B指针往后走；两者相等，说明A该元素在B里存在，直接跳过。

这个方案的时间复杂度是排序O(n log n + m log m)加上扫描O(n + m)，在数据量大时比双重循环快好几个量级。代价是需要额外空间存两个排序结果链表，以及写一个插入排序。如果不想自己写排序，也可以用归并排序的思路对链表排序，效果是一样的。

实际项目中我还会做一个补充处理：如果A里有重复元素，排序后相同的值会相邻，扫描时加一个判断“当前值等于上一个值时跳过”，顺便就把去重做了。这一步看起来小，但对结果正确性影响很大。

7. 我写链表时真实掉进去过的坑

写完那么多代码，最后聊点实在的。我在项目里和教学里见过太多链表bug，这里挑四个最有代表性的说，个个都是真实踩过的坑。

7.1 指针指到自己，链表原地打转

有一次我写的遍历输出死活停不下来，终端光标一直跳，最后发现原因是构建链表时，某个节点的next被误设成了自己。单节点自环还好发现，要命的是长链表里某处悄悄形成小环，遍历到那里就无限循环。

排查方法很简单：遍历时加一个计数器，超过总节点数N就报错退出。更早预防的方法是：每次修改next前，用纸笔画一遍“当前指针从哪来、要往哪去”，画对了再写代码。

7.2 删除节点之后继续访问它

delete之后的节点，内存已经归还，data和next都是无效的，继续访问就是悬垂指针。我见过最隐蔽的一种是：删除节点时把结果存到局部变量里，后面不小心又用了这个局部变量。C++不会报错，因为它读的是已经释放的内存，表现就是“有时候正常，有时候崩”。

正确做法是：删除节点后把它立刻置空，并且养成“谁删除谁负责，删除后绝不再用”的习惯。

7.3 头指针传参丢了头

这是新手问得最多的一个问题。void insertAtHead(Node* head, int val)看上去没问题，可函数里执行head = newNode之后，外面打印链表发现什么都没变。原因就是传的是指针的值拷贝——head本身是变量，保存一份地址，把这个变量传进去，函数里改的是副本，改不到外部的真实头指针。

解决方法是前面代码里那样用Node*& head，或者在函数里返回新的头指针：Node* insertAtHead(Node* head, int val)，用返回值覆盖外部变量。两条路都行，但要形成固定习惯，别混着用。

7.4 调试链表最快的方式：画图和打印

链表代码出bug时，不要急着改，先把链表画出来。左箭头右箭头一画，哪个指针接错了，一目了然。打印也很有用，尤其是对比插入、删除、逆置前后的输出。我写链表必配一个打印函数，这个习惯救过我太多次。

最后再分享一个小技巧：写链表题先处理空链表和单节点这两个极端情况，再处理普通情况。极端情况代码量不大，但能挡住一半的崩溃。只要把“空、单、多”三种情况都验证过，这段链表代码基本就稳了。链表的代码量不大，难在指针逻辑的严谨性，手写几遍之后，你对内存和指针的理解会上一个台阶，这是任何框架和高级语言都替代不了的基本功。