尾插法实现有序链表交集：思路、代码与避坑指南

这道题我太熟悉了好多学校的机考、考研复试上机题里都有它的身影。表面上是求两个有序链表的交集实际上考察的是对链表遍历、内存管理、边界条件处理的综合能力。很多同学卡住并不是因为“求交集”这个逻辑想不出来而是在细节处理上栽跟头——比如空链表怎么输出、重复结点怎么处理、结果链表怎么高效构造。这次我把自己做题的完整思路、代码实现、踩过的坑全部整理出来包含验证过的测试用例希望能帮大家把这道题彻底吃透。1. 整体设计与核心思路拆解1.1 题目到底在考察什么先看题目要求给定两个递增有序的链表输出它们的交集序列。这个“递增有序”是关键前提它直接决定了我们能用最高效的归并思路去扫描两个链表而不是用O(n*m)的暴力双重循环去逐个比对。我做题前习惯先划分这道题的知识点链表的创建头插法还是尾插法插入顺序对结果有什么影响。有序链表的归并思想两个指针分别遍历值小的先走值相等则记录。结果链表的构造如何保持输出递增有序同时保证内存不泄漏。1.2 为什么首选尾插法题目名字里就带了“尾插法”这其实是出题人给出的重要暗示。头插法插入新结点是放在头结点之后这会导致链表最终逆序存储——如果你用头插法构造一个看似递增的序列遍历输出时得到的会是对应的递减序列直接偏离题目要求的“从小到大输出”。尾插法的核心维护逻辑是链表里始终记录一个尾指针tail每次新结点都挂到tail后面再让tail向前移动。这样做的好处有三个构造出的链表天然是输入顺序不用额外逆置。求交集时结果链表按比较顺序插入本身就是递增的。代码逻辑直观不容易出现指针悬挂错误。有些同学可能会想既然头插法会导致逆序那我最后写一个链表翻转函数不就行了吗理论上可以但代码量会增加、出错概率也提高在线考试里属实没必要自找麻烦。1.3 主函数的场景设计主函数里要读取的是两个链表的元素个数和数据。第一行是第一个链表的结点个数空格分隔若干数值第二行同理。这里有一个容易踩的坑读取数据不能用for循环直接在scanf后面接数字因为你不知道题目给的测试数据是不是恰好换行分隔。比较稳妥的做法是用while循环配合scanf的返回值来判断while (scanf(%d, val) ! EOF) { // 读到的是有效整数就尾插进链表A }但这样做的风险是你没法区分“链表A结束”和“链表B开始”。所以更好的方案是先按行读个数再按行读数据用for循环强制按给定个数接收scanf(%d, n1); for (int i 0; i n1; i) { scanf(%d, val); creat(A, val); }这个方案最贴近题目描述只要测试数据格式不出问题读取就是可靠的。1.4 算法复杂度推导先说结论时间O(nm)空间O(nm)的极端情况是结果集等于两个链表的完整交集且每个结点都新建我们分析的是附加空间。两个链表都只扫描一遍分别消耗n和m次比较。每次比较是O(1)所以整体时间O(nm)。如果最终交集有min(n,m)个结点尾插会为每个结果结点分配一次内存空间O(min(n,m))。相比暴力法的O(n*m)时间这个效率提升在长链表测试上非常明显。如果你在后面做OJ题时有耗时限制这个分析可以作为你优化之前的基准线。2. 核心结构与代码实现2.1 链表结点的定义与工具函数#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *List;用typedef把Node和List定义好后面传参写起来干净很多。创建头结点和尾插插入这两个操作是每个链表题的基础建议单独写函数void initList(List *head) { *head (Node*)malloc(sizeof(Node)); (*head)-next NULL; } void tailInsert(List head, int val) { Node *tail head; while (tail-next ! NULL) { tail tail-next; } Node *newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; tail-next newNode; }注意tailInsert每次都要从头遍历到末尾——这是给只有几十个结点的链表用的写法没问题。但如果你追求更完美的写法可以在init时把尾指针存下来或者直接在create阶段就用尾插不依赖重复遍历的方式。我这里为了清晰度先用简单版本实际考试里性能完全可以过。2.2 用尾插法构建有序链表题目明确输入数据本身就是递增的所以我们不需要排序直接尾插即可。完整的数据读取与建链表逻辑如下List A NULL, B NULL; initList(A); initList(B); int n1, n2, val; scanf(%d, n1); for (int i 0; i n1; i) { scanf(%d, val); tailInsert(A, val); } scanf(%d, n2); for (int i 0; i n2; i) { scanf(%d, val); tailInsert(B, val); }这个步骤的用意是把数据存放和算法逻辑解耦。算法本身关心的是链表遍历与比较输入数据的合法性比如到底是不是有序的不归算法模块管。真实机考中也建议这样分层设计出了问题容易定位。提示如果输入数据不保证递增你需要在建链表前做排序。但这不是本题的考察点而且会增加复杂度不建议多此一举。2.3 核心merge函数一次扫描求交集求交集的核心逻辑是用两个指针pA和pB分别从两个链表的首元结点开始遍历。因为两个链表都是递增的所以可以用经典的“归并比较”思路如果pA-data小于pB-datapA向后移动一步因为A的当前元素已经不可能出现在B的后续序列里了。如果pA-data大于pB-datapB向后移动一步原因对称。如果相等说明找到了一个交集元素将其尾插到结果链表然后两个指针同时后移一步。这个思路看起来简单首次接触的读者可能疑惑为什么小的元素可以直接丢弃而不是暂存因为两个链表都是递增的较小的那个元素如果在另一个链表中出现过它的位置一定在另一个链表当前指针的后面。但另一个链表的当前元素就已经比它大了后续全部元素只会更大所以这个“较小元素”绝对不可能在另一个链表后续出现。这就是有序性带来的数学上的单调性保证。List intersectList(List A, List B) { List res NULL; initList(res); Node *pA A-next; Node *pB B-next; Node *tail res; while (pA ! NULL pB ! NULL) { if (pA-data pB-data) { pA pA-next; } else if (pA-data pB-data) { pB pB-next; } else { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data pA-data; newNode-next NULL; tail-next newNode; tail newNode; pA pA-next; pB pB-next; } } return res; }这个函数就是全题的核心。代码不长但每一步都有明确的逻辑支点。这里再强调一个细节当pA和pB相等时我们只把pA的数值复制到新结点然后让新结点的next置空。你有没有想过为什么不直接让结果的尾指针指向pA这个结点原因很直接如果让结果链表的结点复用了原链表的结点那你输出结果是没问题但后续如果要求你不破坏原链表或者你在结果链表上做删除等操作就会直接影响到原链表的结构。考试里比较规范的写法是新建结点保证数据独立性。如果题目明确说“可以释放原有的两个链表”那可以复用但为了安全和通用性我给的建议是新建结点。2.4 打印与内存释放的细节输出格式要求如果交集为空输出“NULL”否则从第一个元素开始输出元素之间用空格分隔末尾不能有多余空格。void printList(List L) { Node *p L-next; if (p NULL) { printf(NULL\n); return; } int first 1; while (p ! NULL) { if (first) { printf(%d, p-data); first 0; } else { printf( %d, p-data); } p p-next; } printf(\n); }那个first变量就是用来处理末尾空格问题的。很多同学写循环直接“printf(%d , p-data)”最后多出来一个空格在OJ里通常也会判错。内存释放也不能省略。有的同学觉得程序退出后系统会回收内存不写free也没关系。但这里要提醒的是计算机专业课的上机考试甚至有些公司的笔试环境会动态检测内存泄漏。习惯性地写一个freeList函数既展示了你对内存管理的理解也避免线上测试工具向你抛出“内存泄漏”警告。void freeList(List L) { if (L NULL) return; Node *p L; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } }注意这个写法不是销毁链表之后就不管了它从第一个结点开始逐结点保存下一个指针再释放当前结点释放完一个结点之后还能继续向后遍历不会出现访问已释放内存的危险。2.5 完整代码汇总#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node, *List; void initList(List *head) { *head (Node*)malloc(sizeof(Node)); (*head)-next NULL; } void tailInsert(List head, int val) { Node *tail head; while (tail-next ! NULL) { tail tail-next; } Node *newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; tail-next newNode; } void printList(List L) { Node *p L-next; if (p NULL) { printf(NULL\n); return; } int first 1; while (p ! NULL) { if (first) { printf(%d, p-data); first 0; } else { printf( %d, p-data); } p p-next; } printf(\n); } void freeList(List L) { if (L NULL) return; Node *p L; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } } List intersectList(List A, List B) { List res NULL; initList(res); Node *pA A-next; Node *pB B-next; Node *tail res; while (pA ! NULL pB ! NULL) { if (pA-data pB-data) { pA pA-next; } else if (pA-data pB-data) { pB pB-next; } else { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data pA-data; newNode-next NULL; tail-next newNode; tail newNode; pA pA-next; pB pB-next; } } return res; } int main() { List A NULL, B NULL; initList(A); initList(B); int n1, n2, val; scanf(%d, n1); for (int i 0; i n1; i) { scanf(%d, val); tailInsert(A, val); } scanf(%d, n2); for (int i 0; i n2; i) { scanf(%d, val); tailInsert(B, val); } List ans intersectList(A, B); printList(ans); freeList(A); freeList(B); freeList(ans); return 0; }我在本地用多个用例跑过这个代码输出完全正确内存释放也正常。3. 边界条件与避坑指南一个很多人忽略但考试必考的点两个链表都可能为空。如果链表A长度为0那么结果应该直接是NULL。我的merge函数里pA和pB都是NULL进不了while循环自然返回空链表打印输出NULL这没问题。还有一种情况两个链表有交集但某个链表只扫描了一半就结束了。比如A:[1 2 3 4]B:[1 2]。扫描到pA指向3、pB为NULL时循环结束结果链表只有[1 2]正确。因为B已经全部遍历完A剩余的元素不可能出现在B里了。这里要理解的是即使A后面还有更大的值最终结果也不可能包含它们因为B里没有剩余元素可供匹配。重复值的处理也非常值得说道。题目说的是有序链表如果A里有重复元素比如[1 1 2 2]B里有重复元素[1 2 2]那么交集理论上应该怎么算这里要分两种理解集合意义上的交集重复元素只算一次交集是[1 2]。多重集合意义上的交集重复元素按出现次数计算交集是[1 2 2]A里2出现两次B里2出现两次取最小出现次数为2。多数OJ按第一种理解也就是重复值只保留一个。但如果你真按“只保留一个”来处理又有一个新问题A[1 1 2]B[1 2]用双指针扫描时会得到怎样的顺序pA1pB1相等插入1pA后移到第二个1pB后移到2。pA1pB21小于2pA后移到2。pA2pB2相等插入2结束。 结果[1 2]恰好符合集合交集要求。但如果A是[1 2 2]B是[1 2 2]呢过程是插入1pA到2pB到2。插入2pA到第二个2pB到第二个2。插入2pA和pB都为NULL结束。 结果[1 2 2]。这又变成了多重集合意义上的交集。这说明直接用双指针相等则插入的做法在出现连续重复值时会把重复值也插入结果。如果题目要求严格集合语义你得在插入前加一个判断如果结果链表最后一个元素的值等于当前相等值就跳过不插入。这个判断需要你维护一个tail指针并查看tail-data。我查了这道题在不同评测平台上的原题描述大部分情况下测试数据都是不含重复元素的或者即使有重复也不会刻意卡你这个点。但作为要拿满分的同学我建议你直接把去重逻辑写进merge函数一劳永逸else { if (tail res || tail-data ! pA-data) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data pA-data; newNode-next NULL; tail-next newNode; tail newNode; } pA pA-next; pB pB-next; }这里tail初值等于res头结点所以条件tail res用来判断结果链表是否为空为空时可以插入。这道题的边界案例我整理成了表格方便大家对照验证自己的代码测试场景输入A输入B预期输出常规相交1 3 5 72 3 6 73 7完全相交1 2 31 2 31 2 3完全不相交1 2 34 5 6NULLA为空空1 2 3NULLB为空1 2 3空NULL一长一短1 2 3 4 51 51 5单元素相交888单元素不相交79NULL含负数和零-5 -1 0 3-5 0 2-5 0我最初做题时在“完全不相交”这个用例上栽过跟头。原因是我在打印之前判断pANULL || pBNULL就提前输出NULL忽略了还有一种情况是两个链表都有剩余元素但始终没有相等值。比如A:[1 2 3]B:[4 5 6]pA和pB都不为空会一路比较到pANULL最后结果链表还是空。如果只在循环前判断就会漏掉这种情况输出一个空行而不是NULL。所以正确统一的处理方式就是循环结束后统一交给printList去判断不要在merge里提前打印。4. 链表操作的三个进阶注意点4.1 头结点的作用我定义的链表类型是带头结点的。有些教材或者同学习惯用不带头结点的指针变量直接存储首元结点在遍历、判空、插入时都需要单独讨论“是否首个元素”的分支代码容易写乱。带头结点之后链表是否为空统一判断head-next NULL插入和遍历都从head-next出发逻辑一致边界条件少很多。这个习惯建议大家养起来凡是写链表题一律带头结点没必要让自己多操心。4.2 指针移动的时机在merge函数的while循环里注意相等分支的三个动作顺序先插入新结点并更新tail再让pA和pB同时向后移动。这三个动作的顺序不能乱。如果你先移动pApA指向的下一个结点可能依然等于pB那后续的比较逻辑就变了结果会多出重复元素。如果你先修改tail而没有移动pA那下次循环会再次比较同一个值造成死循环或者重复插入。我自己写码时有个习惯每次移动指针之后都在心里默念一句“移动之后pA和pB指向的结点必须满足有序扫描的性质”这样可以避免很多低级错误。4.3 内存泄漏的预防整段代码里malloc出现了三处头结点初始化两处交集函数里新建结点。如果写漏了free在本地运行你可能看不出问题但大型测试数据下内存会一直增长严重时超内存限制。如果你发现OJ报“Memory Limit Exceeded”而你的算法空间明明不大那大概率是内存泄漏或死循环造成的无限新建结点。排查思路先把freeList注释掉跑一遍测试用例再恢复注释重新跑看有没有不同的运行结果。如果只是内存差异那问题就在回收逻辑上。5. 复杂度分析与两种进阶扩展5.1 时间复杂度与空间复杂度的直观类比线下聊天的时候我常跟同学打一个比方如果把求交集比作两个人在翻两本按照时间顺序排列的日记暴力法就是A每翻一页B就要把整本日记翻一遍去找有没有相同日期。而双指针法更像是两个人各持一本日记同时从第一天往后翻谁的日期小谁先往后翻翻到两个人日期相同就记录然后两人一起往后翻。你只翻一遍两个人手上的日记都是有序的你绝不会往回翻。O(nm)的推导也来自这里。while循环每一次迭代至少会让pA或pB后移一个结点就算两个指针同时后移也只会消耗min(n,m)次指针不同时后移的情形总消耗不超过nm次。所以整体循环次数与两个链表长度线性相关。5.2 进阶扩展一不新建结果结点如果题目允许复用原来的结点你可以把找到的相交结点从原链表里“拆”下来接到结果链表末尾然后把原链表剩余部分释放掉。这样的空间复杂度从O(min(n,m))降到了O(1)只额外使用几个局部指针变量。不过这个做法的前提是题目明确允许修改原链表或者在调用后再也不需要访问原链表。如果题目只是输出交集而不要求保留原链表我就建议直接在merge函数里改动原链表省掉新建结点的开销和内存释放步骤。但如果你是在线考试环境除非你对题意十分确定否则还是使用保守的新建结点方案风险最低。5.3 进阶扩展二用数组辅助实现如果面试时你面前没有现成的链表环境也可以把两个链表分别读入数组再用数组的双指针求交集。这个思路跟链表双指针几乎一模一样只是把“pA指针”换成数组下标i把“pB指针”换成数组下标j。int i 0, j 0, k 0; while (i n1 j n2) { if (arrA[i] arrB[j]) { i; } else if (arrA[i] arrB[j]) { j; } else { ans[k] arrA[i]; i; j; } }数组版本有一个天然优势你不需要手动管理链表节点的next指针代码更短出错率更低。输入要求数据量已知用动态数组完全合适。但链表版本作为数据结构基本功是必须掌握的。5.4 为什么尾插法在求交集中如此关键回到题目里那个“尾插法”三个字。其实求交集这个场景对插入方式的要求非常严格你在遍历过程中发现一个相等元素时这个元素一定比上一个结果元素大或者相等如果不去重的话。如果把新结点头插到结果链表那结果链表就变成了递减输出顺序最后还得做一次链表反转。尾插法的好处是直接按“从小到大的发现顺序”构建链表构造过程和算法的输出要求完全同构。换句话说这道题选择尾插法不是随便哪个插入方法都行的“体力活”而是由“输出递增序列”这个需求反向推导出的必然选择。这也是为什么我建议在复习链表时把插入方式作为“设计策略”的一部分去理解而不是当成固定模板背下来。理解了这一点你在面对“合并两个有序链表”、“求两个有序链表的并集”这类题时会有一种“题目还没读完解法已经在脑子里成型”的感觉。我自己常做的一个训练是每完成一道链表题就把它的插入方式换一下问问自己如果改成头插法会怎样改成在指定位置插入会怎样。多试几次你就能体会出不同插入方式在不同场景下的优劣而不是只会照着模板敲代码。最后再分享一个小建议写完代码后一定要自己设计边界数据跑一遍不要只依赖OJ的测试点。我就是在本地把“单元素相交”、“完全不相交”、“一个链表为空”这种极端用例都测过之后才在机考时做到一遍过。数据结构这玩意儿代码量少坑却不少多花十分钟测试省下的是考场上反复提交和怀疑人生的时间。