先声明一下我不是题目AC完就丢的那种人刷题时我更在意把一道题吃透。PTA上这道“两个有序链表序列的交集”就是这么被我反复折腾过的题。网上搜这题的大多是课程作业党也有准备考研机试的。我以为这道20分的题核心难点其实不在“求交集”的算法本身而在于——你选的解法能不能在PTA那台裁判机上跑得稳以及你的链表操作基本功过不过关。这篇内容我不想罗列官方答案那种冷冰冰的代码而是站在一个踩过坑的人的视角拆解这道题从读题到AC的全过程顺便把链表的几个关键操作原理讲透。文章按我的思路拆成几块先分析题目真正在考什么再给出两种常用解法并说明为什么我推荐双指针然后贴出完整可跑的C代码接着讲我实测时踩过的坑和调试方法最后聊聊这个方法还能用在哪些地方。1. 题目到底在考什么别被“20分”骗了PTA把这道题标了20分放在题目集里属于中等偏简单的位置但它的信息量一点都不少。我先把题目完整梳理一遍方便还没做过这道题的朋友直接对照。题目要求读入两个递增有序链表都是非递减排列求它们的交集输出时也要求递增有序。输入格式是两行每行是一串以-1结尾的整数序列-1本身不属于序列数据。输出只有一行就是交集序列如果交集为空则输出NULL。表面上这题考的是“求两个有序集合的交集”但“集合”两个字太容易让人往哈希表、布尔数组那个方向想了。真正重要的是题目里反复强调的两个词有序和链表。有序意味着你可以利用单调性做线性归并链表意味着你要在指针层面操作节点而不是像数组那样随意按下标访问。接下来我说说这题实际在抽查哪几个能力点很多同学在这些地方翻车链表构建能力。PTA的链表题通常不会给你现成的建链代码你得自己读数据、动态分配节点、尾插法建链。尾插法的细节尤其是最后一个节点的next置空没写对后面遍历就会死循环或者段错误。归并交集的双指针逻辑。这题和“合并两个有序链表”长得像但交集要求保留相等元素。指针移动的三种情况小于、大于、等于你要能在纸上画清楚代码才不会乱。内存管理的习惯。题目没说要不要释放内存但OJ上跑完程序进程会自动回收。可你要是自己写笔记、自己跑测试特别是用内存检测工具比如Valgrind的时候不释放节点就会报泄漏。别问我怎么知道的。对边界条件的敏感度。两行输入都可能为空行吗第一行直接是-1呢交集结果为空时输出NULL这时换行怎么处理这些细节决定你是过样例还是AC。我来用一个生活化的类比帮你建立直觉想象你手里有两串按价格从低到高排列的商品标签要找同时出现在两串里的商品。最笨的办法是拿第一串的每个标签去第二串里从头翻一遍聪明的办法是两串各放一个手指头谁便宜谁往后移动一样贵就记录并同时往后移动。第二种办法就是双指针归并也是这题的标准解法。2. 两种主流解法的对比为什么我推荐双指针而非标记法在确认题目要求之后接下来要选实现方案。很多第一次做这道题的同学会想到这样几种做法我挨个点评一下。方案一借助“标记数组”或“哈希表”求交集思路是这样把第一条链的所有值存进一个布尔数组或者哈希集合然后遍历第二条链如果某个值已经在集合里就输出。你可能会觉得这做法很直观但它有几个问题题目没说数值范围。如果数据是int范围内的任意整数开一个几百万大小的标记数组要么栈溢出要么空间浪费严重。输出顺序不容易保证。虽然两条链都是有序的但如果你遍历第二条链那么得到的交集天然有序这算是个安慰。可如果要求按第一条链的顺序输出就得多存一轮。这做法本质上还是“空间换时间”对于链表题来说考官想看的通常是你对指针操作的掌握而不是你调用哈希表。方案二两个指针同步扫描双指针归并这是教科书上标准的线性求交集方法。两条链各维护一个指针从头开始比较如果pa-data pb-data说明pa指向的元素在第二条链中不可能有匹配因为pb已经是最小的未比较元素了让pa后移如果pa-data pb-data同理让pb后移如果相等记录这个值然后pa和pb同时后移。为什么它高效因为每一轮比较至少让一个指针前进两个指针一共最多走lenA lenB步时间复杂度是O(nm)空间复杂度是O(1)。最关键的是这完全就是链表场景下最自然的解法——你只需要每个节点访问一次不需要回头。我直接给你画个简单的流程感假设A链是1-2-3-5B链是2-3-4。pa指向1pb指向212pa指向2pa2pb2相等记录2pa指向3pb指向3pa3pb3相等记录3pa指向5pb指向454pb后移发现是NULL结束。交集就是2 3。你看整个过程像不像两组人排队谁矮谁往前走一步身高一样就拉出来记一笔。所以我的建议很明确这道题用双指针归并法不但代码短而且不会引入额外的空间复杂度也符合数据结构课程对链表操作训练的要求。标记法适合数据范围小、以数组为存储结构的题目在这种链表题里属于“能过但不是好解法”。3. 手把手写代码从链表定义到AC的完整实现方案定下来接下来就是动手实现。我直接给出我用的是纯C语言版本因为PTA的老题目对C的兼容性最好而且考研机试也常用C写。我这个代码是完整可提交的不只是核心片段。先定义链表节点。这里有个小习惯我想分享节点结构体用typedef取别名后面写LNode *p比写struct Node *p省事很多也减少因为漏写struct造成的编译错误。#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;接下来是建链函数。输入以-1结束我用尾插法。为什么用尾插因为要保持链表顺序和输入顺序一致。如果用头插法读入1 2 3得到的是3 2 1顺序就反了。LinkList ReadList() { LinkList head (LinkList)malloc(sizeof(LNode)); head-next NULL; LNode *tail head; int x; while (scanf(%d, x) x ! -1) { LNode *p (LNode *)malloc(sizeof(LNode)); p-data x; p-next NULL; tail-next p; tail p; } return head; }注意head是一个头节点哨兵节点它本身不存有效数据。这样做的好处是即使链表为空head指针也永远有效插入和删除操作不需要对“第一个节点”单独做特殊判断。这是数据结构课本里经典的“带头节点链表”强烈建议养成这个习惯。然后是核心的交集函数。这个函数不创建新链表直接在原链上按双指针逻辑遍历找到相等的值就打印。当然更“数据机构课”的做法是创建一个新链表保存交集节点然后统一输出。我两种都写一下你先看直接打印的版本void IntersectPrint(LinkList A, LinkList B) { LNode *pa A-next; LNode *pb B-next; int flag 0; // 标记是否已经输出过元素用来处理空格 while (pa pb) { if (pa-data pb-data) { pa pa-next; } else if (pa-data pb-data) { pb pb-next; } else { if (flag 0) { printf(%d, pa-data); flag 1; } else { printf( %d, pa-data); } pa pa-next; pb pb-next; } } if (flag 0) { printf(NULL); } printf(\n); }这段代码有一个容易被忽略的细节空格处理。如果你在每个元素后面都输出一个空格PTA的裁判机通常也能接受它们一般会忽略行尾空格但如果你把空格放在元素前面第一个元素前就不能有空格。我习惯用flag标志来防止多打空格这样输出格式最干净。完整的主函数就非常简洁了int main() { LinkList A ReadList(); LinkList B ReadList(); IntersectPrint(A, B); return 0; }直接打印的思路简单直接但有些同学可能会问如果老师要求返回一个交集链表而不是直接打印怎么办那就把“打印”的部分改成“创建新节点”把相等的值复制过去。整体逻辑一模一样只是把printf换成malloc tail插。我贴一下这种“创建新链表”的写法方便课程设计要求返回链表的朋友直接用LinkList Intersection(LinkList A, LinkList B) { LinkList C (LinkList)malloc(sizeof(LNode)); C-next NULL; LNode *tail C; LNode *pa A-next; LNode *pb B-next; while (pa pb) { if (pa-data pb-data) { pa pa-next; } else if (pa-data pb-data) { pb pb-next; } else { LNode *p (LNode *)malloc(sizeof(LNode)); p-data pa-data; p-next NULL; tail-next p; tail p; pa pa-next; pb pb-next; } } return C; }两种写法放在一起你就能看出核心的双指针逻辑完全一样区别只在于“命中相等元素后干什么”。这其实是个很好的学习点算法逻辑和输入输出解耦代码结构就能灵活复用。4. 实测复盘我在调试时撞上的三个坑代码看起来已经能跑但真实OJ和课设环境往往会给你意外的惊喜。我把自己实际调试中遇到的三个坑详细拆一遍这些才是真正的经验值。4.1 空行输入的坑题目给出的样例输入是这样的1 3 5 7 9 -1 2 4 6 8 10 -1但如果输入行只有-1呢比如第一行直接是-1第二行是1 2 -1。这时ReadList读完第一个-1直接返回一个只有头节点的空链表IntersectPrint里pa是NULL循环进不去flag是0输出NULL。看起来没问题。但有一种情况会翻车有些同学用scanf的返回值判断输入结束写了while (scanf(%d, x) ! EOF x ! -1)。如果测试数据里在-1之后还有多余的空白字符这种写法没问题但如果输入的行首有换行或空格也没问题scanf会跳过空白。真正的问题是——如果题目输入本身是两行而你用EOF判断时没注意行数第一次读列表把第二行的数据也读进去了。所以我的建议是严格按题目规则以-1作为一条链的结束标志不要用EOF判断一条链的结束。4.2 死循环问题我最早写的循环条件不够严谨写成while (pa ! NULL || pb ! NULL) { if (pa-data pb-data) pa pa-next; ... }只要有一个指针已经是NULLpa-data这行就会触发空指针访问在OJ上表现为段错误Runtime Error。还有一种更隐蔽的问题如果你忘记在相等时同时移动两个指针或者在某一个分支写错移动对象就可能出现pa一直停在原地、pb一直在走直到走出链表又回到NULL判断最终死循环。我调试这类问题的方法很土但非常有效在循环里加一个计数器每轮循环加1超过lenA lenB 5就强制退出并打印标志。确认是死循环之后再用“两个指针移动日志”的办法打印每一轮pa和pb指向的值一眼就能看出哪个分支写错了。4.3 输出格式NULL和空格题目要求交集为空时输出NULL。怎么判断交集为空看有没有输出过任何数字。所以必须有个flag或者用链表C是否为空来判断。如果采用“先建链表再输出”的写法判断C-next NULL即可。但如果采用直接打印的写法别用pa NULL来判断——因为循环结束有两种可能要么pa为空要么pb为空并不能说明一定有交集或没有交集。比如A链为空但B链非空循环结束时pa是NULL但交集就是空再比如A链和B链有交集但已经输出完了此时pa也可能是NULL。所以必须依赖“是否输出过元素”这个标志。5. 内存泄漏和链表释放隐藏的课设扣分点很多同学把这个题AC之后就关页面了但如果你是在做课程设计或者实验报告老师很可能要求你写内存释放。我再补一个释放函数这属于链表基本功void FreeList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *q p-next; free(p); p q; } }调用方式int main() { LinkList A ReadList(); LinkList B ReadList(); IntersectPrint(A, B); FreeList(A); FreeList(B); return 0; }这个释放函数有个细节必须在free(p)之前把p-next存到q里否则free之后再去读p-next就是访问野指针。顺序反了就是未定义行为Valgrind会提示Invalid read。如果你用Windows下的Dev-C跑内存泄漏看不出来但如果你用Linux下的gcc配Valgrind就会看到类似definitely lost: 40 bytes in 2 blocks的报错。课程设计如果要求做内存检查不释放链表直接扣分不冤。所以我一律建议写完核心功能之后把释放函数和输入输出函数一样看成必写部分。这里顺带提一个实用的调试技巧在链表开头加头节点哨兵节点之后释放链表时也会把这个头节点一起释放掉所以FreeList从传入的L开始free是正确的不用特殊处理头节点。6. 完整验证我测试过的一组边界用例为了确保代码在各种边界条件下都能AC我整理了下面这些测试用例你可以复制到PTA的自定义测试里跑一遍。表格里的“预期输出”是用上面的代码实测得到的结果。用例A链输入B链输入预期输出说明样例11 3 5 -12 4 6 -1NULL完全无交集样例21 2 3 -11 2 3 -11 2 3完全重合样例3-11 2 -1NULLA为空链样例41 2 3 -1-1NULLB为空链样例51 1 2 2 -11 2 2 3 -11 2 2有重复元素体现“非递减”样例65 -15 -15单元素相等样例71 3 -12 3 4 -13交错排列这里最有迷惑性的是样例5。题目说的是“非递减”序列允许重复。求“交集”时重复元素怎么算按数学上集合的定义重复元素应该去重但很多PTA题目语境下的“交集”其实是多重集交集也就是两个序列里都出现多少个就保留多少个。比如A链有两个1B链有一个1交集保留一个1A链有两个2B链有两个2交集保留两个2。我写的双指针逻辑天然支持这种多重集交集——因为相等时我只让两个指针各走一步没有跳过重复值。如果你用标记数组并且把重复值去重样例5的输出就会和我的不一样。做这道题前最好确认一下你们课设或OJ对交集的定义PTA这题我实测是多重集语义也就是我代码里的行为。同样的道理也适用于“合并两个有序链表”那道题——如果两条链里有相等元素是保留一个还是两个题目要求不同代码逻辑就不同。读懂题目语义再动手比急着写代码重要得多。7. 从这题延伸到其他经典题双指针的通用性这道题AC了但它带来的方法可以帮你解决一票同族问题。我觉得这个部分才是这道20分小题的隐藏价值。第一个延伸合并两个有序链表PTA 7-XX类似题。核心逻辑几乎一样只是把“相等”分支从打印交集变成把两个节点都接进结果链。代码结构上你需要多处理一个“剩余链整体接入”的步骤因为合并时如果一条链走完了另一条链剩下的部分可以直接拼上去。而求交集时剩下没走完的部分不可能再匹配直接不用管。第二个延伸求两个有序链表的差集。也就是A中有但B中没有的元素。双指针照样能走pa-data pb-data时说明pa元素不在B中记录pa并后移pa-data pb-data时pb后移相等时两个都后移。你会发现这几种操作的代码模板是同一个差别只有每个分支里“做什么动作”。第三个延伸链表的归并排序思想。归并排序的merge步骤本质上也是双指针操作两条有序链。很多同学在学排序时觉得归并排序很难其实如果你先把这道交集的题吃透了再看归并排序的merge代码会发现就是同一个骨架换了一层皮。第四个延伸求两个有序数组的交集。思路完全通用只要把链表指针换成数组下标就行。如果在笔试环节遇到数组版求交集我脑子里弹出的第一个解法就是双指针。我建议你做完这题之后顺手把“合并两个有序链表”“删除有序链表中的重复元素”“求两个有序链表的并集”这几道题一起刷了。刷完你会发现它们本质上在考同一套双指针/归并套路只是细节动作不同。最后说一下我在多次带学生做这道题时观察到一个共性很多人不是不会双指针而是不会画图。我强烈建议你在草稿纸上画出两条链用两个手指头或者两个小方块代表指针一步步走一遍。只要这个过程走顺了写代码就是翻译动作而已。如果你能走到这一步这道20分的题就不是拿分题而是帮你打通链表操作任督二脉的入门题。