企业官网建设流程全解析

先声明一下：我不是题目AC完就丢的那种人，刷题时我更在意把一道题吃透。PTA上这道“两个有序链表序列的交集”就是这么被我反复折腾过的题。网上搜这题的大多是课程作业党，也有准备考研机试的。我以为这道20分的题，核心难点其实不在“求交集”的算法本身，而在于——你选的解法能不能在PTA那台裁判机上跑得稳，以及你的链表操作基本功过不过关。这篇内容我不想罗列官方答案那种冷冰冰的代码，而是站在一个踩过坑的人的视角，拆解这道题从读题到AC的全过程，顺便把链表的几个关键操作原理讲透。文章按我的思路拆成几块：先分析题目真正在考什么，再给出两种常用解法并说明为什么我推荐双指针，然后贴出完整可跑的C代码，接着讲我实测时踩过的坑和调试方法，最后聊聊这个方法还能用在哪些地方。

1. 题目到底在考什么：别被“20分”骗了

PTA把这道题标了20分，放在题目集里属于中等偏简单的位置，但它的信息量一点都不少。我先把题目完整梳理一遍，方便还没做过这道题的朋友直接对照。

题目要求读入两个递增有序链表（都是非递减排列），求它们的交集，输出时也要求递增有序。输入格式是两行，每行是一串以-1结尾的整数序列，-1本身不属于序列数据。输出只有一行，就是交集序列，如果交集为空则输出NULL。

表面上这题考的是“求两个有序集合的交集”，但“集合”两个字太容易让人往哈希表、布尔数组那个方向想了。真正重要的是题目里反复强调的两个词：有序和链表。有序意味着你可以利用单调性做线性归并；链表意味着你要在指针层面操作节点，而不是像数组那样随意按下标访问。

接下来我说说这题实际在抽查哪几个能力点，很多同学在这些地方翻车：

• 链表构建能力。PTA的链表题通常不会给你现成的建链代码，你得自己读数据、动态分配节点、尾插法建链。尾插法的细节（尤其是最后一个节点的next置空）没写对，后面遍历就会死循环或者段错误。

• 归并交集的双指针逻辑。这题和“合并两个有序链表”长得像，但交集要求保留相等元素。指针移动的三种情况（小于、大于、等于）你要能在纸上画清楚，代码才不会乱。

• 内存管理的习惯。题目没说要不要释放内存，但OJ上跑完程序进程会自动回收。可你要是自己写笔记、自己跑测试，特别是用内存检测工具（比如Valgrind）的时候，不释放节点就会报泄漏。别问我怎么知道的。

• 对边界条件的敏感度。两行输入都可能为空行吗？第一行直接是-1呢？交集结果为空时输出NULL，这时换行怎么处理？这些细节决定你是过样例还是AC。

我来用一个生活化的类比帮你建立直觉：想象你手里有两串按价格从低到高排列的商品标签，要找同时出现在两串里的商品。最笨的办法是拿第一串的每个标签去第二串里从头翻一遍；聪明的办法是两串各放一个手指头，谁便宜谁往后移动，一样贵就记录并同时往后移动。第二种办法就是双指针归并，也是这题的标准解法。

2. 两种主流解法的对比：为什么我推荐双指针而非标记法

在确认题目要求之后，接下来要选实现方案。很多第一次做这道题的同学会想到这样几种做法，我挨个点评一下。

方案一：借助“标记数组”或“哈希表”求交集

思路是这样：把第一条链的所有值存进一个布尔数组（或者哈希集合），然后遍历第二条链，如果某个值已经在集合里，就输出。你可能会觉得这做法很直观，但它有几个问题：

1. 题目没说数值范围。如果数据是int范围内的任意整数，开一个几百万大小的标记数组要么栈溢出，要么空间浪费严重。
2. 输出顺序不容易保证。虽然两条链都是有序的，但如果你遍历第二条链，那么得到的交集天然有序，这算是个安慰。可如果要求按第一条链的顺序输出，就得多存一轮。
3. 这做法本质上还是“空间换时间”，对于链表题来说，考官想看的通常是你对指针操作的掌握，而不是你调用哈希表。

方案二：两个指针同步扫描（双指针归并）

这是教科书上标准的线性求交集方法。两条链各维护一个指针，从头开始比较：

• 如果pa->data < pb->data，说明pa指向的元素在第二条链中不可能有匹配（因为pb已经是最小的未比较元素了），让pa后移；
• 如果pa->data > pb->data，同理让pb后移；
• 如果相等，记录这个值，然后pa和pb同时后移。

为什么它高效？因为每一轮比较至少让一个指针前进，两个指针一共最多走lenA + lenB步，时间复杂度是O(n+m)，空间复杂度是O(1)。最关键的是，这完全就是链表场景下最自然的解法——你只需要每个节点访问一次，不需要回头。

我直接给你画个简单的流程感：假设A链是1->2->3->5，B链是2->3->4。pa指向1，pb指向2，1<2，pa指向2；pa=2，pb=2相等，记录2，pa指向3，pb指向3；pa=3，pb=3相等，记录3，pa指向5，pb指向4；5>4，pb后移发现是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; ... }

只要有一个指针已经是NULL，pa->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的自定义测试里跑一遍。表格里的“预期输出”是用上面的代码实测得到的结果。

这里最有迷惑性的是样例5。题目说的是“非递减”序列，允许重复。求“交集”时重复元素怎么算？按数学上集合的定义，重复元素应该去重，但很多PTA题目语境下的“交集”其实是多重集交集，也就是两个序列里都出现多少个就保留多少个。比如A链有两个1，B链有一个1，交集保留一个1；A链有两个2，B链有两个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分的题就不是拿分题，而是帮你打通链表操作任督二脉的入门题。