先说个题外话第一次看到这个题号“7-52”和题目名字里那个“come Boby!”我以为是哪本教材的课后题混进了什么奇怪的东西。实际做下来才发现这道题虽然分值只有20分但它把链表题里最经典的两个考点全占了——有序链表的线性比较和尾插法建链。如果你能把这道题吃透后面遇到“合并两个有序链表”“删除重复元素”这类题基本就是同一套思路换皮。这篇文章我就把我自己的完整推导过程、踩坑记录和最终代码都摊开讲适合刚学完链表、正在刷题或者期末复习的人对照着看。1. 这道题到底在考什么题目拆解与两个前置认知1.1 题目要求的三个关键信息原题描述其实很短核心就三句话给定两个按值递增排列的有序链表求它们的交集输出结果链表。但越是短题目隐含信息越密我先把它拆开“有序”是整道题最大的红利。两个链表都是非递减排列这意味着我们不需要用哈希表去重也不用嵌套两层循环去暴力比较完全可以用两个指针同时扫扫一遍就能出答案。“交集”在链表语境下指的是“值相同的节点集合”。注意这里不要求节点地址相同只看节点的数据域是否相等。所以交集中的每个值在两条链里都必须至少出现一次。输出结果链表的顺序。因为输入链表是有序的所以交集天然也是有序的。题目隐含要求输出时也必须是递增的否则判题机直接给零分。我当时第一眼看到这题脑子里冒出的第一个方案是“把链表A的每个节点拿去链表B里挨个找”——这就是典型的暴力解。但这么做的复杂度是O(n×m)而且链表不像数组没法随机访问B链每次都要从头走到尾数据量稍微大一点就直接超时。20分的题不会这么粗暴一定有个更聪明的做法。1.2 链表题的一个关键习惯先画图再写码做链表题最忌讳一上来就写代码。我自己的习惯是先在草稿纸上画三个链表链表A、链表B、结果链表C然后用两个手指头当指针模拟一遍移动过程。你会发现但凡指针移动的规则没想清楚代码里就会出现空指针解引用、死循环、漏节点这类问题。后面我会把指针怎么走画成非常直白的文字描述你照着在纸上画一遍就通了。另外还要想清楚一个问题结果链表C的节点是“新建”的还是“从原链表拆下来的”这道题的标准做法是新建节点——也就是找到相等值的时候malloc一个新节点把值复制进去再挂到结果链表末尾。这么做的好处是原链表A和B完全不受影响代码逻辑干净内存管理也简单。有些进阶版本会让你直接拆原链表的节点去复用那是为了省内存不是这题的要求。2. 从暴力嵌套到双指针思路推导的完整过程2.1 暴力法为什么不行我先把最直观的暴力解法写出来不是为了让你用它而是为了对比出双指针的优越性。暴力法的思路是// 伪代码对A中每个节点遍历B寻找相同值 p A-next; while (p ! NULL) { q B-next; while (q ! NULL) { if (p-data q-data) { // 找到了尾插到C break; } q q-next; } p p-next; }这个代码在思路上是对的但有两个大问题时间复杂度O(n×m)。假设A有1万个节点B也有1万个节点最坏情况下要比较1亿次判题机直接告诉你超时。如果B链很长每次从头扫前面已经比较过的区域全被浪费了。因为链表没有随机访问能力你甚至没法像数组那样二分。所以暴力法只适用于“两个链表都非常短”的教学演示真要提交是不行的。2.2 有序带来的核心红利指针不用回溯两个链表都是有序的这给我们的最大启示是如果A当前节点的值比B当前节点小那么A这个节点绝不可能出现在B的“当前节点之后”的任何位置——因为B后面的节点值只会更大只会比A的当前值更大。这句话是整个算法的灵魂。它意味着当A的值小于B的值时A的那个节点可以直接丢掉指针往后挪一格反之如果B的值小于A的值B的指针往后挪。两个指针永远不会回头最多把A和B各遍历一遍总复杂度是O(nm)。这跟“归并排序里合并两个有序数组”的思路一模一样。你甚至可以把它理解为排队打饭两列人都按身高从矮到高排好了只要比较队头的两个人矮的那个一定不会是另一个队伍里任何人的交集直接出队。两边队头一样高就记下来两队同时出队。2.3 三种情况的处理规则设两个指针p和q分别指向链表A和B的头节点这里我用带头节点的链表p和q初始都指向第一个有效节点。每一轮比较只有三种情况情况条件处理动作情况一p-data q-datap的值太小p往后移一位情况二p-data q-dataq的值太小q往后移一位情况三p-data q-data找到共同值新建节点尾插到Cp和q同时后移这里有个细节很多人会忽略情况三为什么p和q要同时后移因为有序链表里可能存在重复值比如A链是1 2 2 3B链是2 2 4。如果只在p往后移、q不动那么下一轮p指向第二个2q还指向第一个2又会匹配一次这可能没问题但如果你只想要每个值出现一次就需要额外处理。标准题目里“交集”的定义通常是按值去重后的结果也就是说2 2和2的交集应该输出2而不是2 2。所以我建议在情况三里p和q同时后移这样天然去重。如果你希望保留重复次数即多重集交集那就要改成只移动较小的那个或者按计数处理——但那不是这题的要求不要想多了。2.4 尾插法和头插法的选择逻辑确定了比较规则接下来要解决“找到共同值之后怎么挂到结果链表上”。这里有两种思路头插法每次新节点都插在链表头部。好处是代码短不需要维护尾指针坏处是结果链表是逆序的最后必须做一次反转。尾插法每次新节点都挂在链表末尾需要一个尾指针rear不断更新。好处是结果顺序天然正确坏处是写代码时要多维护一个指针。这两个方法本身没有优劣但放在这道题里尾插法是正解。原因很简单输入是有序的比较过程中找到的公共值也必然是有序的你用头插法等于人工制造逆序还得额外交一次反转纯粹是给自己找麻烦。而且尾插法是链表操作的基本功如果这里练熟了后面写“多项式加法”“队列的链式存储”都会顺很多。3. 尾插法的核心实现与代码逐段拆解3.1 结构体定义与创建链表的辅助函数老规矩先定义节点结构体和建链函数。这里我用带头节点的单链表好处是统一处理空表和非空表插入删除都不需要特判头指针。#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 尾插法创建链表读入n个数据返回带头节点的链表头指针 LinkList createList(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); head-next NULL; LinkList rear head; // 尾指针始终指向最后一个节点 for (int i 0; i n; i) { LinkList newNode (LinkList)malloc(sizeof(LNode)); scanf(%d, newNode-data); newNode-next NULL; rear-next newNode; rear newNode; // 更新尾指针 } return head; }注意一个细节createList里我也用了尾插法因为题目要求“输入序列就是链表顺序”尾插最直接。如果这里你图省事用头插法那读入1 2 3结果链表变成3 2 1后面还得反转不划算。3.2 求交集函数双指针扫描 尾插拼接这是全题的核心我先把代码完整贴出来然后一行一行解释。// 求两个有序链表的交集结果存入新链表返回其头指针 LinkList intersection(LinkList A, LinkList B) { // 结果链表的头节点哨兵节点不存数据 LinkList C (LinkList)malloc(sizeof(LNode)); C-next NULL; LinkList rear C; // 结果链表的尾指针 LinkList p A-next; // 指针p遍历链表A LinkList q B-next; // 指针q遍历链表B while (p q) { // 任一链表遍历完交集就不可能再增加了 if (p-data q-data) { p p-next; } else if (p-data q-data) { q q-next; } else { // 相等产生一个交集节点 LinkList newNode (LinkList)malloc(sizeof(LNode)); newNode-data p-data; newNode-next NULL; rear-next newNode; rear newNode; // 尾指针后移 p p-next; q q-next; // 两指针同时后移 } } return C; }几个关键点是我写的时候反复确认过的while循环的终止条件是p q也就是“两个指针都不为空”。为什么因为交集的定义是“同时存在于两个链表中”只要有一个链表已经走到末尾剩下的节点就算值再大再小也绝对不可能在另一条链里找到匹配了所以直接结束。malloc一个新节点再复制数据而不是直接把p或q节点接到C上这是为了避免破坏原链表结构也避免两个链表和结果链表之间产生共享节点带来的野指针隐患。尾指针rear的更新时机每次挂新节点后rear newNode。这一步忘了写的话结果链表会一直往第二个节点后面挂形成环或者丢失节点。这种bug特别隐蔽编译能过跑起来也不报错但输出就是不对。相等时p和q同时后移这个我在前面已经解释过是为了去重。你可以试着手动模拟一次A 1 3 5 5 7B 3 5 5 8如果只动p不动q第一个5匹配成功后p到了第二个5q还在第一个5又会匹配一次结果就变成3 5 5这显然不对。3.3 遍历输出与释放内存输出函数没什么花活但这里有一个判题机特别在意的细节行末不能有多余空格。我自己的处理方式是输出第一个节点前不给空格之后每个节点前加一个空格这样最后一个节点后面就没有尾随空格了。void printList(LinkList L) { LinkList p L-next; int flag 0; // 0表示还没输出过节点 if (p NULL) { printf(NULL\n); return; } while (p ! NULL) { if (flag 1) { printf( ); } printf(%d, p-data); flag 1; p p-next; } printf(\n); }“交集为空时输出什么”不同题目要求不一样。有的平台要求输出NULL有的要求什么都不输出还有的要求输出空行。我在提交前会先确认题目的输出样例。如果样例里交集为空时显示了NULL那就按NULL来如果样例里是空行那就改成只打一个换行。这个问题看似小事但很容易成为20分扣成10分的原因。内存释放倒不是OJ判题必须的但作为一个好习惯尤其是你在自己的机器上跑的时候我还是建议把释放函数写上void freeList(LinkList L) { LinkList p L-next; while (p ! NULL) { LinkList tmp p; p p-next; free(tmp); } free(L); }3.4 完整可运行代码把上面几个函数拼起来再加上main函数就是完整的可提交版本#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; LinkList createList(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); head-next NULL; LinkList rear head; for (int i 0; i n; i) { LinkList newNode (LinkList)malloc(sizeof(LNode)); scanf(%d, newNode-data); newNode-next NULL; rear-next newNode; rear newNode; } return head; } LinkList intersection(LinkList A, LinkList B) { LinkList C (LinkList)malloc(sizeof(LNode)); C-next NULL; LinkList rear C; LinkList p A-next; LinkList q B-next; while (p q) { if (p-data q-data) { p p-next; } else if (p-data q-data) { q q-next; } else { LinkList newNode (LinkList)malloc(sizeof(LNode)); newNode-data p-data; newNode-next NULL; rear-next newNode; rear newNode; p p-next; q q-next; } } return C; } void printList(LinkList L) { LinkList p L-next; if (p NULL) { printf(NULL\n); return; } int flag 0; while (p ! NULL) { if (flag) printf( ); printf(%d, p-data); flag 1; p p-next; } printf(\n); } int main() { int n, m; scanf(%d, n); LinkList A createList(n); scanf(%d, m); LinkList B createList(m); LinkList C intersection(A, B); printList(C); return 0; }代码贴完了但你先别急着复制去提交。我建议你至少手动跑三组测试数据分别是有交集的普通情况、完全没有交集的情况、某个链表为空的情况。跑完再提交基本一枪过。4. 边界条件与隐藏扣分点我实测中踩过的几个坑4.1 坑一尾指针忘了更新结果链表丢了后半截这个坑我印象太深了。有一次我把rear newNode这行注释掉去测试输入4 1 2 3 4 3 2 3 5理论上交集应该是2 3。结果程序输出只有2。为什么因为每次新节点都挂在了同一个rear后面——也就是C的头节点后面第一个新节点后面其实被第二个新节点覆盖了这个新旧节点第二个节点的地址只在某个临时变量里存着链表的next却一直指向第二个节点所以第二个节点丢失。这种bug非常典型尤其是刚学尾插法的人写着写着就把尾指针的更新忘了。我的检查方法是每一处尾插操作必须同时出现“挂接”和“更新尾指针”两个动作只看到一个就必须停下来问自己是不是漏了。4.2 坑二行末空格导致格式错误很多OJ对输出格式的判断是逐字符对比的行末多一个空格都算格式错误。比如你写printf(%d , p-data);最后一个节点后面就多了一个空格判题机直接报Presentation Error或者Wrong Answer。我见过不少同学在这上面扣了冤枉分尤其是题目分值本来就不高扣一点就很不划算。我的方案就是那个flag变量。你也可以换一种写法第一次输出不打空格之后每次先打空格再打数字。效果一样选哪个都行关键是脑子里要有“行末空格是错”这根弦。4.3 坑三空链表和空交集的区分题目可能给出长度为0的链表也就是n 0。此时createList(0)返回的头节点的next是NULLintersection里的p A-next也是NULL循环直接不执行C是空链表printList(C)输出NULL。这个逻辑本身没问题但很多人在main里判断输入为0时就直接特判了结果特判逻辑写错反而画蛇添足。我的建议是不要对长度0做特殊处理让统一的代码自然处理它。因为链表代码里空链表在逻辑上和“没有交集”是同一回事代码路径是一样的。你只需要确保createList(0)返回一个合法的头节点不要返回NULL就行。4.4 坑四比较时用了或导致死循环还有个新手容易犯的错误写比较的时候把小于写成小于等于。比如if (p-data q-data) { p p-next; } else if (p-data q-data) { q q-next; }这会导致什么当p-data q-data时走进了第一个分支只有p后移了q原地不动。下一轮p指向了新值如果这个新值比q还大又走第二个分支让q后移……这样绕来绕去既可能错过公共值也可能造成死循环。相等的情况必须单独列出来并且两个指针一起动这是我写这类题的最低原则。4.5 关于测试用例的自我检查清单每次写完链表题我习惯用下面这张表做自测。你如果每次都能把这张表里的用例跑一遍再提交基本能避免90%的隐藏扣分测试场景链表A链表B期望输出普通交集1 3 5 72 3 5 83 5无交集1 2 34 5 6NULL完全相同1 2 31 2 31 2 3完全包含1 2 3 42 32 3重复值1 2 2 32 2 42一条空链(空)1 2 3NULL单节点相等777负数与前导数据-5 -1 0 3-3 -1 0 5-1 0这里特别说明一下“重复值”那行。如果题目要求的是“多重集交集”那你的输出应该是2 2而不是2。我前面给的双指针同时后移的做法输出是2也就是去重后的交集。绝大多数20分的基础题都是按去重来判的但保险起见你要去看题目里有没有“结果中不得包含重复元素”之类的字眼。如果没有明确写再结合样例去猜出题人的意图。5. 三种解法的复杂度对比与这道题的推广价值5.1 暴力、哈希、双指针谁才是最优解我把自己能想到的三种解法放在一起对比一下方便你理解为什么最终选择双指针解法时间复杂度空间复杂度是否适合此题原因暴力嵌套循环O(n×m)O(1)不适合数据量大时超时哈希表辅助O(nm)O(n)可以但不推荐需要额外建表且链表题考的就是指针操作双指针线性扫描O(nm)O(1)最合适利用有序性省时省空间代码简洁哈希表的思路其实也值得一提先把A链所有节点的值放进哈希表再遍历B链如果B的值在哈希表里出现过就输出到结果链。但这对链表题来说有点“作弊”因为它没有用到“链表有序”这个核心条件而且如果你自己实现哈希表代码量会大不少用C语言更是没有现成的容器可以用。在数据结构课程里这道题就是想让你练指针移动的不是练哈希。5.2 掌握这道题之后能秒杀的几类变种说实话这类“两个有序序列合并/求交/求差”的题在大学数据结构题库里有一整个家族。你把这题吃透了下面这些就都是换汤不换药两个有序链表的合并核心思路一模一样只是相等时选一个接入另一个后移最后把剩余部分直接接上。两个有序链表的差集A有B没有的值同样是三指针比较只是相等时不做插入而是双指针后移。两个有序数组的交集把链表换成数组指针换成下标算法完全一样。三个有序链表的公共元素用三个指针找三者相等的时候插入否则移动最小的那个指针。我自己后来做“合并K个有序链表”这种题底层的小逻辑也还是这个——两两比较选最小的出来。可以说双指针线性扫描是链表操作里最通用的基本功之一。5.3 最后再分享一个我个人的调试技巧如果你在自己的环境里跑这道题输出不对时别急着改代码我建议你在intersection函数里临时加几句打印把每一轮的p-data和q-data都打出来while (p q) { // 临时调试代码提交前删掉 // printf(当前比较: p-%d, q-%d\n, p-data, q-data); if (p-data q-data) { // ... } }这么一看你就立刻知道是哪一步的指针没动或者哪一步进错了分支。很多链表bug都是“指针走位”的问题眼睛盯着代码看不出来但把每轮比较的值打出来一秒就定位了。调试完记得把这些临时打印删干净不然输出格式会直接崩。我早年就干过这种事调试输出忘了删提交后输出一堆奇怪东西全场最低分别提多尴尬。这道题本身不难但它是链表操作的一块试金石。能独立写出这个双指针版本你对尾插法、空指针判断、边界条件的感觉就已经过关了。写错没关系重要的是知道错在哪、为什么错——毕竟链表这玩意儿就是靠一路踩坑踩出来的经验。