1. 题目拆解与考点评判1.1 这道题到底在考什么第一次看到 “7-52 两个有序链表序列的交集”很多人第一反应是这不就是把两个链表扫一遍求公共元素吗好像很简单。但真拿到PTA上提交反复报错的人才明白这道20分的题坑点全在链表操作的工程细节上而不是算法思想上。题目本身很直白给定两个递增排列的整数链表输出它们的交集序列要求交集元素按原序输出如果交集为空输出NULL。没有复杂的多测试用例也没有刁钻的格式陷阱但它刻意把数据组织成了“链表”而不是数组。这意味着你不能用i去随便访问第几个元素只能一个结点一个结点地从前往后走。这么做的好处是逼你把“指针”、“结点”、“链式存储”这些基本功练扎实坏处是——代码稍微粗心一点段错误和段错误之后的一片空白就会轮番轰炸你。我在帮学生调这道题的时候最清晰的感觉是80% 的人不是不会求交集而是不会“安全地”读入链表、不会“正确地”遍历链表、不会“干净地”控制输出格式。所以这篇文章不会只丢一份能过的代码给你而是把从读入到输出、从边界到扩展的完整链路都拆开讲一遍。1.2 适用于哪些场景和人群如果你是以下三类人这篇内容应该对你有直接帮助正在刷 PTA 数据结构题目集的学生尤其是被 7-52 卡过或担心被卡的同学准备数据结构期末或考研需要把链表操作和双指针思想过一遍的人刚学完 C 语言、想入门算法题对“为什么这样写才对”充满疑惑的新手。顺带一提这道题在考研和面试题里经常以变形方式出现比如“两个有序数组合并成有序数组”、“求两个有序数组的中位数”、“合并两个有序链表”等。把这道题的逻辑吃透后面遇到那些题你会发现核心都是同一个套路利用有序性用双指针线性扫描。2. 核心思路为什么双指针是正解2.1 最朴素的做法与它的代价先说一个很多人一开始的直觉把链表 A 的每个结点都拿到链表 B 里去遍历一遍看是否存在相同的值。代码很好写两层循环就完了但问题在于时间复杂度是 O(n×m)。如果两个链表各有 10000 个结点最坏情况要比较 1 亿次这在 OJ 上基本就是超时的代名词。虽然这道题数据量不一定大到这个程度但数据结构题考查的就是你有没有“利用前提条件优化思考”的意识。题目的前提是“有序”而且是递增序。这个条件一旦存在就说明一个关键事实当链表 A 当前结点的值小于链表 B 当前结点的值时A 的当前值永远不会再出现在 B 的后续结点中因为 B 后续结点的值只会更大。同样如果 B 当前值小于 A 当前值B 的当前值也永远不会出现在 A 的后续结点中。这就为双指针线性扫描提供了理论基础。2.2 双指针扫描的过程拆解具体做法可以这样描述用两个指针pa和pb分别指向两条链表的第一个数据结点然后反复执行如果pa-data pb-data说明当前值就是交集的一部分。输出这个值然后把两个指针都向后移动一步如果pa-data pb-data说明 A 的当前值偏小它不可能与 B 中更大的值相等直接让pa指向下一个结点如果pa-data pb-data意思相反则让pb指向下一个结点。这个过程重复到其中一条链表已经走完就可以立即停止。因为交集元素必然同时出现在两条链表中如果有一条链表已经走到末尾另一条剩下的部分无论多大都不可能再被当前指针指到相同的值了。拿生活里的例子类比两个人各拿一叠升序编号的卡片想找出相同编号。每次比较双方手里的最上面一张编号小的那位就翻掉这张因为对方手里已经不可能有更小的了相等就取出来各翻一张。两个人中任何一个人的卡翻完了游戏就结束。整个过程不需要回头也不会有遗漏。这样做的时间复杂度是 O(mn)也就是两条链表长度之和。额外空间是 O(1)因为你只是移动指针没有新建辅助数组或链表。2.3 为什么不用哈希表也有同学会想先把一条链表的所有值塞进哈希表然后遍历另一条链表查表时间复杂度平均也能到 O(mn)而且代码更“现代”。这个思路本身没问题在 Java 或 Python 里用HashSet确实很方便。但在 PTA 的 C 语言环境里哈希表你得自己造内存分配、冲突处理都是额外负担而且这道题的课程目标显然是练链表和指针操作用哈希表属于“绕开了考点”。退一步讲就算允许用哈希表它也有一点小麻烦题目要求输出交集元素“按原序”也就是按递增顺序输出。如果先建表再遍历另一条链表得到的顺序取决于第二条链表的遍历顺序恰好也是递增的所以没问题。但哈希表的空间复杂度是 O(m)比双指针的 O(1) 差一些。在算法题里能用指针线性扫描解决的有序问题优先用双指针这是通用经验。3. 完整的 C 语言实现与逐步精读3.1 链表结构定义与读入函数首先定义一个最简单的单链表结点typedef struct Node { int data; struct Node *next; } Node;读入链表时我习惯用一个head头结点不存数据作为统一入口。这样无论链表是否为空头指针都有效遍历和后续操作都不用写一堆if (head NULL)的特判。Node* readList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; Node *tail head; int x; while (scanf(%d, x) 1 x ! -1) { Node *p (Node*)malloc(sizeof(Node)); p-data x; p-next NULL; tail-next p; tail p; } return head; }这个函数的几个细节值得说清楚用tail记录当前链表的最后一个结点每次新结点直接挂在tail后面然后更新tail这叫尾插法。尾插法可以保证链表顺序与输入顺序一致终止条件是读到-1也就是题面给定的输入结束标记scanf的返回值判断为 1确保每一次都确实读到了一个整数这一步在 OJ 上通常不是必须的但养成习惯能规避一些诡异输入格式导致的问题。这里提醒一句有些同学会把p (Node*)malloc(sizeof(Node))写错成sizeof(p)这往往会分配一个指针大小的内存不够存整个结点后续写入data和next时就会缓冲区越界产生难以排查的段错误。sizeof的对象应该是Node结构体本身不是指针。3.2 主程序双指针求交集读入两条链表之后核心逻辑非常短int main() { Node *la readList(); Node *lb readList(); Node *pa la-next; Node *pb lb-next; int printed 0; // 是否已经输出过元素用于控制空格 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { if (printed 0) { printf(%d, pa-data); printed 1; } else { printf( %d, pa-data); } pa pa-next; pb pb-next; } else if (pa-data pb-data) { pa pa-next; } else { pb pb-next; } } if (printed 0) { printf(NULL); } return 0; }输出格式上有个常见坑题目要求数字之间用一个空格分隔但末尾不能有多余空格。这里用printed变量记录是否已经输出过数字第一个数字前不打印空格后面的数字统一打印“空格数字”这样既满足了分隔要求又不会在末尾多出空格。从逻辑正确性来看双指针循环里最需要注意的是只有当两个值相等时两个指针才同时移动不等时只移动较小值所在链表的指针。把这一步写成“两个指针都移动”是新手最常见的错误会导致跳过了可能相等的元素。比如 A 链有 1、3B 链有 1、3第一次相等取 1 后两个指针同时到 3这是对的但如果 A 链有 1、2、3B 链有 1、3第一次相等取 1 后同时移动A 指针到 2、B 指针到 3此时 2 小于 3A 指针继续移到 3然后相等取 3最后输出 1 3结果正确。原理上正是“较小值单方移动”保证了不会遗漏任何可能的相等值。3.3 关于内存释放与空链表PTA 的判题程序不会检查你是否free释放内存写完直接返回也不会被扣分。但从学习角度我仍然建议你在 return 0 之前把两条链表都释放掉养成好习惯。释放的基本写法是从头结点开始逐个保存next再free当前结点void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p-next; free(p); p tmp; } }另一个值得专门提的点是空链表。如果输入就是-1读入函数返回一个只含头结点、没有数据结点的链表la-next为NULL。此时 while 循环根本不会进入printed保持为 0输出NULL逻辑完全正确。这正是带头结点的好处如果不用头结点空链表时你就得写成pa NULL后面每一处访问pa-data之前都要检查是否为空麻烦得多。3.4 一份可以直接提交的完整代码把上面的片段拼起来就是一个可以直接提交的完整版本#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* readList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; Node *tail head; int x; while (scanf(%d, x) 1 x ! -1) { Node *p (Node*)malloc(sizeof(Node)); p-data x; p-next NULL; tail-next p; tail p; } return head; } int main() { Node *la readList(); Node *lb readList(); Node *pa la-next; Node *pb lb-next; int printed 0; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { if (printed 0) { printf(%d, pa-data); printed 1; } else { printf( %d, pa-data); } pa pa-next; pb pb-next; } else if (pa-data pb-data) { pa pa-next; } else { pb pb-next; } } if (printed 0) { printf(NULL); } return 0; }这份代码我本地用 GCC 编译验证过配合题目样例输入可以正常输出预期结果。缺少freeList只在实际开发中算问题在 OJ 提交里不构成扣分点。但如果你的学校要求检查内存泄漏就把它加上反正没坏处。4. 常见错误与调试实录4.1 段错误最常见的三个来源这道题报Segmentation fault的频率相当高原因基本集中在三处。第一读入链表时没有把 head 初始化为 NULL也没用头结点。有些人喜欢直接定义全局指针然后scanf循环分配如果第一次分配失败或链表为空后面访问head-next就会操作一个无效地址。带头结点后这个风险基本消失。第二循环里访问已经被置为 NULL 的指针。典型错误写法是这样while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { printf(%d, pa-data); pa pa-next; pb pb-next; } }表面看没错但如果pa-next已经是 NULL而两个值恰好又相等一次循环的下一次判断会先检查pa ! NULL不会进去访问数据所以这个写法其实安全。真正容易崩的是类似写法中在循环体内无条件访问pb-data却没有在每次循环开头保证它非空。建议在循环条件里同时检查两个指针不要一个检查一个不检查。第三malloc 之后没有判断返回值。在 OJ 上一般不会内存不足但学校本地的老旧实验环境偶尔会出现一次性创建大量结点失败。稳妥的做法是分配后判断if (p NULL)就报错退出。这在平时练习里不算必须但如果你在写一个通用工具函数加上会有帮助。4.2 输出格式与空集判定的坑输出NULL是这道题最容易忽视的一点。很多人把交集为空的情况漏掉或者把NULL写成了null、None或者多打了一个换行符。PTA 题目明确规定空集输出大写的NULL必须以题面为准。我见过一个学生因为输出NUL被扣了 4 分自己怎么查都查不出逻辑问题最后才发现是笔误。还有一点交集中如果有多个相同值怎么办由于题目给定链表序列是“递增排列”递增序列里同一个值不会重复出现所以正常输入下不需要额外处理重复。但如果你自己构造测试数据时不小心给了一个链表中出现两个连续的 5双指针逻辑会输出两次 5这在严格集合语义下并不严谨。稳妥的做法是在相等分支里输出后用while (pa-next pa-next-data pa-data)跳过连续重复值对pb也做同样处理。虽然原题用不到但这种防御性写法是好的面试时也能帮你堵住边界。4.3 样例自测与常见数据检验我自己调试这类题目时一般至少会测试以下几组数据两个链表有交集例如1 2 3 4 -1和3 4 5 -1预期输出应包含3 4其中一个为空例如-1和1 2 3 -1预期输出NULL两个都为空预期输出NULL完全相同的链表输出所有元素没有交集例如1 2 -1和3 4 -1预期输出NULL一个是另一个的子集例如1 3 5 -1和1 2 3 4 5 6 -1。把这六组跑完基本能覆盖这道题的全部边界条件。遇到 Wrong Answer 时我特别建议先在本地把这六组样例都过一遍再回去看代码。很多 WA 其实不是题解思路错而是输出格式或边界处理不干净。5. 扩展与进阶从这道题到更广的算法视野5.1 用 Java 实现的思路对照这道题也可以用 Java 写JDK 自带的LinkedList类能省去很多指针操作。双指针逻辑完全一样只是把ListNode next换成了 Java 集合里的迭代器或下标访问public static ListInteger intersection(ListInteger a, ListInteger b) { ListInteger res new ArrayList(); int i 0, j 0; while (i a.size() j b.size()) { int va a.get(i), vb b.get(j); if (va vb) { res.add(va); i; j; } else if (va vb) { i; } else { j; } } return res; }Java 版本的好处是不用纠结指针是否悬空但代价是get(i)在LinkedList里是 O(n) 的随机访问所以如果底层用的是LinkedList这种写法反而不如 C 语言的指针高效。更地道的 Java 做法是用ListIterator来遍历本质上还是两个迭代器并行移动。这个细节说明算法思想不变但语言接口不同实现的复杂度会有差异。5.2 与经典题目的联系这道题的骨架其实就是很多面试题的原型。最接近的是 LeetCode 160“相交链表”只不过那里求的是两条链表在物理上是否共用一个结点。再往上延展LeetCode 21“合并两个有序链表”也是双指针扫描只不过合并时把较小的一个不断插入结果链表。还有 LeetCode 349“两个数组的交集”和 350“两个数组的交集 II”分别对应去重与不去重两种版本。如果把有序条件换成无序那么思路就要改成先排序或哈希表。一道题变化出来的几个方向恰好是面试里常被追问的“如果输入条件变了你的方案怎么调整”。所以别觉得 7-52 只是作业把它吃透面试时你就有了一张可以随时翻出来的底牌。5.3 关于复杂度分析的几个极端情况双指针方案的时间复杂度稳定在 O(mn)空间复杂度为 O(1)。但在分析时要注意一个容易混淆的点如果其中一条链表特别短比如 B 只有 1 个元素循环依然最多走 m1 次因为每次比较要么移动 A 指针要么移动 B 指针B 指针到达尾部后循环立即结束。这个复杂度上界不会因为一方短而退化成 O(m*n)。反过来想如果你选择“遍历 A 的每个元素在 B 里用二分查找”单次查找是 O(log n)总复杂度 O(m log n)。当两条链表都特别长、且长度差距很大时这种方案在某些情况下可能优于双指针。但考虑到链表本身不支持 O(1) 随机访问除非用跳表或额外数组在链表结构下双指针仍然是综合最优的选择。这个对比也说明复杂度分析必须结合数据结构本身的访问成本不能只数比较次数。5.4 题目变体如果要求交集结果也保存在链表里一个常见的课后变体是不求直接输出而是要求把交集元素构造为一个新链表返回。这和原题的区别是你要在一个双指针循环里不断创建新结点、串成新链表。代码逻辑基本不变只需要把printf换成新链表的尾插操作。这种情况下注意最后要记得给新链表末尾挂 NULL否则遍历时无法判断结束又会出现段错误。如果你正在准备考试建议把这道变体亲手写一遍写完后你会对“链表作为返回值”这个模式有更直观的理解。我自己习惯把这类题整理进一个“链表必刷清单”清单里包括链表反转、两个有序链表合并、两个有序链表交集、链表倒数第 k 个结点、链表中环的检测。这几个题覆盖了链表操作里绝大部分高频考点。每道题都要求自己能写出双指针版本并且能回答“为什么可以线性扫描”。刷完一遍你会发现链表题不再那么像玄学。最后再分享一个我在实际评测中感触很深的小技巧在 PTA 上如果连续多次 Wrong Answer不要急着改算法先把“输出格式”和“空集特判”这两项全部检查一遍。这道题 20 分算法占 15 分左右格式和边界处理占 5 分左右丢掉那 5 分非常可惜。老老实实用 printf 调试也好断点调试也罢把双指针每一步的移动轨迹打印出来对照一遍通常几分钟就能锁定问题。调试的过程本身也是把“为什么较小时只动一边指针”这个逻辑刻进脑子里的过程。