企业官网建设流程全解析

看到题目标题结尾那行“come Boby!”，估计是某位老兄交作业前随手留的暗号，但这道题本身确实经典得不行。两个有序链表序列的交集，数据结构课必考、笔试面试高频，核心套路就俩：双指针归并比较+尾插法构造新链表。很多同学一看到“链表”就发怵，其实这道题把思路理清楚后，代码量不大，拿满20分很轻松。这篇文章我把整个思考过程、代码实现、以及我当年踩过的坑全部拆开讲一遍，你看完直接能照着写出来。

1. 题目到底在考什么：先把思路用手比划清楚

先说说题目本身。输入是两个递增的有序链表序列，都以-1作为结束标志。你要输出这两个链表中都出现过的元素，也就是交集，输出结果也要按递增顺序排好。如果没有交集，输出NULL。

举个例子：

链表A：1 3 5 7 -1 链表B：2 3 5 9 -1

那么交集中的公共元素就是 3 和 5，最终输出3 5 -1。

这道题表面上是考链表操作，实际上考的是三件事：能不能读懂“有序”这两个字的含金量；能不能用双指针在线性时间内完成比较；以及能不能用尾插法正确构造一条新链表。尤其是尾插法，这几乎是所有链表题的地基操作，很多同学写插入节点时把指针顺序搞反，结果链表变成环或者丢节点，调试半天找不到原因。

1.1 输入里的“-1”是个暗号

先说第一个最容易踩的细节：-1不是数据，它是个哨兵值，告诉你“这一行到这里就结束了”。所以读取的时候要写成类似这样的逻辑：

while (scanf("%d", &x) != EOF && x != -1) { // 把 x 尾插到链表中 }

我见过有同学把-1也当成有效节点插入链表，结果求交集的时候多出一堆莫名其妙的-1。记住，读到-1就停，不要把它存进链表。

那为什么要用-1而不是用回车判断？因为评测系统里所有输入都是连续的字符流，你怎么知道一行结束没有？靠回车判断在不同平台下会出现各种幺蛾子。用-1做终止标记是最稳的约定。

另外还要注意一点：如果第一行直接就是-1，说明这条链表是空的。你的代码必须能处理空链表的情况——空链表和任何链表的交集都是空，输出NULL。这个边界很多人一上来就忽略了。

1.2 “有序”两个字值多少分

如果两个链表都是无序的，想求交集，最朴素的办法是：拿链表A的每个节点，去链表B里挨个找。两个链表长度分别是 n 和 m，最坏情况下时间复杂度就是 O(n×m)。题目数据一大直接超时。

但题目明确说“有序”，递增排列。这意味你可以用双指针归并的思路：

• 指针 pa 指向链表A的头节点，指针 pb 指向链表B的头节点。
• 每次比较 pa 和 pb 指向的元素。
• 谁小，谁的指针就往后走；相等，就是交集元素，记录结果后两个指针一起往后走。

整个过程两个指针都只前进不后退，每个节点最多被访问一次，时间复杂度 O(n+m)。这就是“有序”带来的最大红利。别小看这一步，考试的时候如果你能写出这句话，面试官会觉得你确实理解数据结构，而不是只会背代码。

1.3 尾插法在这里解决什么问题

既然要把交集元素按递增顺序存到新链表里，那就涉及“如何往链表末尾添加节点”。每次添加节点，如果都从头节点开始遍历到末尾，那整体复杂度又会变成 O(n²)，浪费双指针省下来的时间。

解决办法就是尾插法：维护一个tail指针，时刻指向当前链表最后一个节点。每次要插入新节点时，直接让tail->next指向新节点，然后tail后移。插入一个节点的时间是 O(1)，整体插入过程是线性的。

一句话总结：双指针负责“找交集”，尾插法负责“存结果”。两者配合，才是这道题的满分答案。

2. 先别急着写代码：三种解法选型对比

在动手写代码之前，我建议你先在脑海里过一遍所有可行方案，选一个最稳的。这道题我见过三种解法，各有优劣，但最后只有一种适合考试场景。

2.1 方案一：数组存储 + 二分查找

思路是先建两个数组，把链表A的元素读进去，排序好。然后遍历链表B的每个元素，在数组A中用二分查找判断是否存在。存在就加入交集结果。

这种方案的时间复杂度是 O(m log n + n)，空间复杂度 O(n + m)。逻辑上不难，写起来也快。但它有个致命问题：数组长度需要预先确定，或者动态扩容，在 C 语言里多一层麻烦。而且既然题目明说是链表题，你用数组实现，虽然能过，但练习效果就打了折扣。更重要的是，面试时你写数组版，面试官很可能追问“如果数据量大到内存装不下怎么办”，直接把你问住。

2.2 方案二：短链表逐节点扫描长链表

优化一下朴素思路：选择较短的一条链表，遍历它的每个节点，在较长链表里查找是否存在。这样时间复杂度是 O(min(n,m) × max(n,m)) 的折中，但还是乘积级别。如果两表长度都在 10⁵ 级别，乘积是 10¹⁰，铁定超时。除非题目数据量很小，否则不推荐。

2.3 方案三：双指针归并 + 尾插法（推荐方案）

就是我上一节讲的核心思路。时间 O(n+m)，如果只算额外辅助空间，除了结果链表外只需要两个指针和若干个临时节点，辅助空间 O(1)，代码量也只有三五十行。无论考试、作业还是面试现场写题，这都是最优解。

看到这个表，选择就很明确了。接下来我们进入完整实现。

3. 完整实现：从建链表到输出交集的代码拆解

3.1 节点定义和建链表：用带头结点的链表

先定义节点结构：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node, *List;

建链表时我建议使用带头结点的链表。头结点不存数据，只是为了让“空表”和“第一个节点”的插入逻辑统一。如果你不带头结点，那插入第一个节点时得额外判断head == NULL，代码会多出一堆分支。

List createList() { List head = (List)malloc(sizeof(Node)); head->next = NULL; List tail = head; // 尾插法核心：时刻指向最后一个节点 int x; while (scanf("%d", &x) != EOF && x != -1) { Node *p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = NULL; tail->next = p; // 新节点挂到末尾 tail = p; // 尾指针后移 } return head; }

这里有个很容易忽略的细节：每创建一个新节点，必须让它的next先置空。否则p->next是野指针，等到最后判断链表是否结束时，程序访问到非法内存，轻则输出乱码，重则直接崩溃。我见过不少同学在这栽跟头，主函数里调试半天，最后发现是新建节点时没初始化next。

3.2 核心交集算法：三规则定乾坤

两链表建好后，就是整个题目最核心的双指针比较逻辑。我把规则总结成三句话：

1. 若pa->data < pb->data，说明pa指向的元素比pb小，那它不可能在链表B中找到相等值，所以pa右移。
2. 若pa->data > pb->data，同理，pb右移。
3. 若pa->data == pb->data，这就是公共元素，把它尾插到结果链表中，然后pa和pb同时右移。

用伪代码写就是：

while (pa != NULL && pb != NULL) { if (pa->data < pb->data) { pa = pa->next; } else if (pa->data > pb->data) { pb = pb->next; } else { // 相等：插入结果链表 insertByTail(resultHead, pa->data); pa = pa->next; pb = pb->next; } }

我手动走一遍上面那个例子：A 是1 3 5 7，B 是2 3 5 9。

• pa=1，pb=2，1 小于 2，pa 右移到 3。
• pa=3，pb=2，3 大于 2，pb 右移到 3。
• pa=3，pb=3，相等，记录 3，pa 到 5，pb 到 5。
• pa=5，pb=5，相等，记录 5，pa 到 7，pb 到 9。
• pa=7，pb=9，7 小于 9，pa 右移变 NULL，循环终止。

最后结果链表装的是3 5。你看，整个过程就跟两队人排队比身高一样，矮的先出列，一样高的牵手记名，非常直观。

3.3 尾插法构造结果链表：小心指针顺序

现在重点来了，结果链表怎么构造。很多同学知道要插到尾部，但写代码时指针顺序搞错，导致链表断掉。我把尾插法的标准写法拆成四步：

Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = pa->data; newNode->next = NULL; // 第一步：新节点初始化，next 置空 tail->next = newNode; // 第二步：把新节点挂到尾节点后面 tail = newNode; // 第三步：让 tail 指向新节点

这里的核心原则是：先改新节点的 next，再改原尾节点的 next。如果你先执行tail->next = newNode，再执行newNode->next = ...，万一中间出了岔子，新节点的 next 还是野指针，整个链表就悬空了。

另一个容易被忽略的点：每次找到公共元素时，必须新 malloc 一个节点，然后把pa->data的值复制进去。你不能直接把原始链表的节点接进结果链表，因为题目要求的“结果”是一个独立的新链表。如果直接把原节点拿去用，一旦后面你释放原链表，结果链表里的节点也跟着失效了。考试题不一定检查内存释放，但面试官一定会问“你这里为什么重新分配节点”——答不上来就是减分项。

3.4 主函数和输出：NULL 和空格是你最后两道防线

主函数里要做的事：建两链表，求交集，输出结果。

void printList(List head) { if (head->next == NULL) { printf("NULL\n"); return; } Node *p = head->next; int isFirst = 1; while (p != NULL) { if (!isFirst) { printf(" "); } printf("%d", p->data); isFirst = 0; p = p->next; } printf("\n"); }

这里有个特别坑的格式要求：输出所有元素用空格分隔，但行尾不能有多余空格。有些同学直接用printf("%d ", p->data)，结果输出行尾多一个空格，OJ 直接判格式错误，20 分没了。

我的处理方式是用一个isFirst标志位，第一个元素前不打空格，之后每个元素前都补一个空格。这样既美观又完全符合格式要求。

主函数完整代码结构：

int main() { List A = createList(); List B = createList(); List result = getIntersection(A, B); printList(result); return 0; }

3.5 完整代码汇总

下面贴出完整代码，我加了注释，方便你直接对照：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node, *List; // 尾插法创建有序链表 List createList() { List head = (List)malloc(sizeof(Node)); head->next = NULL; List tail = head; int x; while (scanf("%d", &x) != EOF && x != -1) { Node *p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = NULL; tail->next = p; tail = p; } return head; } // 双指针求交集，结果用尾插法构造 List getIntersection(List A, List B) { List head = (List)malloc(sizeof(Node)); head->next = NULL; List tail = head; Node *pa = A->next; Node *pb = B->next; while (pa != NULL && pb != NULL) { if (pa->data < pb->data) { pa = pa->next; } else if (pa->data > pb->data) { pb = pb->next; } else { Node *p = (Node *)malloc(sizeof(Node)); p->data = pa->data; p->next = NULL; tail->next = p; tail = p; pa = pa->next; pb = pb->next; } } return head; } // 输出结果，注意空交集输出 NULL，行尾无空格 void printList(List head) { if (head->next == NULL) { printf("NULL\n"); return; } Node *p = head->next; int isFirst = 1; while (p != NULL) { if (!isFirst) { printf(" "); } printf("%d", p->data); isFirst = 0; p = p->next; } printf("\n"); } int main() { List A = createList(); List B = createList(); List result = getIntersection(A, B); printList(result); return 0; }

这段代码在绝大多数 OJ 上都能直接过。但如果你用的编译器不支持scanf返回EOF的判断，也可以用while (scanf("%d", &x) == 1 && x != -1)，意思更明确：只要成功读到一个整数，且这个整数不是-1，就继续插入。后面这个写法我个人更推荐，可读性更好。

4. 踩坑实况：这几个错我当年反复栽

代码写完了，但真正考试时，前面这些坑足够让你折腾半小时。我这里把所有我见过、踩过的坑整理一遍，按出现频率排序。

4.1 读取输入时没判断 EOF，程序死循环

如果不写!= EOF，当输入行结束后程序会一直尝试读数据，结果x变成垃圾值，链表插入一堆乱七八糟的数字。有些 OJ 上你还会看到输出“答案错误”而不是“运行超时”，因为垃圾值插进去后，程序逻辑全乱套了。

4.2 相等时只移动了一个指针

双指针比较时，如果pa->data == pb->data，必须同时让两个指针右移。我见过不少同学只移动pa，不移动pb。后果是：下一轮 pa 已经指向新元素了，pb 还指着这个已经匹配过的公共元素，如果 pa 恰好又走到一个相同的值，会重复插入同一个元素。比如 A 是1 3 3 5，B 是1 3 5，相等的 3 你会插入两次，但输出结果要的是集合交集，不是多重集交集，这就错了。记住口诀：相等，两边一起走。

4.3 输出行尾空格导致格式错误

这是 PTA 这类 OJ 上最常见的低级失误。明明逻辑全对，样例也过了，一提交就是格式错误。原因就是输出行尾多了空格。我前面给的isFirst标志位写法就是为了解决这个问题。如果题目允许，你也可以用for循环控制下标来判断是不是最后一个节点，但isFirst标志位是最通用的写法。

4.4 新建节点没把 next 置空

细节决定成败。C 语言里 malloc 出来的内存是随机值，不手动置空p->next，它就是个野指针。平时小数据量可能碰巧没事，一旦链表遍历到尾部，野指针让你访问越界内存，程序就崩。

4.5 忘记处理空链表和空交集

两条链表任何一条为空，或者没有任何公共元素，按要求都要输出NULL。但很多同学的代码在head->next为 NULL 时，print 函数依然尝试访问p->data，直接段错误。我建议你不只在 print 里判断空表，在getIntersection函数的入口也可以直接判断一下，提前返回一个空表头，把边界情况处理干净。

4.6 内存泄漏问题：考试不查，面试必问

考试和 OJ 不检查你free了多少次，但面试官一定会问。一个合格的链表题解答，最后应该把 A、B、result 这三条链表都释放掉。虽然面试时不一定要求你真的写出来，但你知道要释放，并且能说清楚哪些节点需要 free，这就是加分项。别忘了头结点也要free，很多同学只释放普通节点，头结点反而漏了。

我把这些坑整理成一个速查表，方便你考试前一天过一眼：

5. 扩展开去：求并集、求差集，一个套路全搞定

可能你已经发现了，双指针归并这个思路绝不仅仅能求交集。只要把比较规则改一下，三种集合运算都能做。

5.1 求两个有序链表的并集

并集的意思是：两个链表中出现过的所有元素，并且递增输出。规则变成这样：

• 若pa->data < pb->data，把 pa 指向的元素插入结果链表，pa 右移。
• 若pa->data > pb->data，把 pb 指向的元素插入结果链表，pb 右移。
• 若相等，任选一个插入结果链表，然后 pa、pb 同时右移。

最后，谁还有剩余节点，就把剩余部分全部链到结果链表末尾。代码和求交集几乎一样，只需要改动一小块。这就是双指针框架的复用性。

5.2 求差集（A 有 B 没有）

差集稍微绕一点，但还是同一套框架。规则是：

• 若pa->data < pb->data，说明 pa 指向的这个元素，在 B 中没有匹配项，属于“A 独有”，插入结果链表，pa 右移。
• 若pa->data > pb->data，说明 pb 指向的元素小，跳过它，pb 右移。
• 若相等，两个都跳过，pa 和 pb 同时右移。

你看，核心框架完全一样，只是“什么时候插入结果链表”的条件变了。理解了这套双指针思想，以后碰到“两个有序序列合并”、“两个有序数组找中位数”这类题，你都会特别有底气。

5.3 面试追问高频点：边界条件有哪些

最后分享一个面试小技巧。当你在白板上写完这道题，面试官大概率会追问：“如果链表是空呢？如果两个链表长度差很多呢？如果全部相同呢？”这些都是送分题，前提是你真懂。

我的建议是，答完基础代码后，主动补充一句：“这个算法在每个节点只被访问一次，整体时间复杂度是 O(n+m)，辅助空间除了结果链表外是 O(1)，对空链表和完全不重合的边界情况也都做了处理。”这句话一说出来，显得你既懂原理又考虑全面，和背代码的候选人一下子就区分开了。

根据我个人经验，这道题最值得反复练习的不是代码本身，而是指针移动的每一步都要在纸上画清楚。多画几遍，双指针和尾插法你就彻底拿下了。最后再送一个小技巧：如果你担心自己的代码在 OJ 上因为格式问题白丢分，写输出函数时统一用isFirst标志位处理空格，这辈子都不会再栽在行尾空格上。