企业官网建设流程全解析

如果你刷过PTA（拼题A）上的“数据结构与算法题目集（中文）”，那对7-52这道题一定不陌生。这道题是“两个有序链表序列的交集”，20分，属于链表操作里非常典型的一道基础题。别小看这20分，它几乎把所有链表操作的坑都集中在一道题里了：输入格式的处理、头结点的使用、双指针的移动逻辑、重复元素的去重、空表输出的格式……一不留神就是各种段错误、答案错误、超时。

我当年做这道题的时候，前后折腾了小半天，倒不是思路有多难，而是很多细节没琢磨透。最近整理题库时又把这题翻出来做了一遍，顺手把完整的解题过程和踩过的坑都记录下来，给正在刷题或者准备考研复试数据结构上机的小伙伴一个参考。

1. 题目分析与整体设计思路

1.1 题目到底在考什么

先说题目要求：给定两个递减的有序整数链表（注意是递减，不是递增），要求输出两个链表的交集序列。输入是两行，每行是一串以-1结尾的整数，代表一个链表的全部节点。输出是交集元素，按原顺序输出。

这道题别看简单，实际上覆盖了链表几个核心考点：

• 链表的建立：如何从输入数据构造出带头结点的链表
• 有序链表的遍历和比较：这是归并思想在交集问题上的应用
• 去重处理：当链表中出现重复元素时该怎么处理
• 边界情况：空链表、完全无交集、链表只有一个节点

20分不是白给的，它要求你能完整实现上述所有动作，而且代码要足够健壮。很多同学做这题翻车，不是在大逻辑上出错，而是在输入处理和空表判断这些边角跟上踩坑。

1.2 为什么优先选择双指针法

求两个有序序列的交集，暴力的做法是双重循环：拿链表A的每个元素去链表B里遍历查找。时间复杂度O(n*m)，n和m分别是两个链表的长度。如果两个链表各有10万个节点，那就要执行10^10次比较，在在线评测系统里几乎必然超时。

另一种思路是用哈希表：先遍历链表A，把所有值存进哈希集合，再遍历链表B，判断每个元素是否在集合里，是则输出。时间复杂度降到了O(n+m)，但需要额外的O(n)空间，而且C语言还得自己实现哈希结构，杀鸡用了牛刀。

这道题的正解是双指针法：因为两个链表都是有序的（递减），我们可以在两个链表上各自维护一个指针，从前往后同时扫描。比如当前A指针指向a，B指针指向b：

• 如果a > b，说明a不可能在B中存在（因为B后面的元素都比b小），A指针向后移动
• 如果a < b，说明b不可能在A中存在，B指针向后移动
• 如果a == b，这个值就是交集元素，输出并同时移动两个指针

双指针法的时间复杂度是O(n+m)，空间复杂度O(1)。既不用额外存储，也不会超时，完全就是为有序链表求交集量身定做的方案。

这里顺便提一句，如果把两个链表从递减改成递增，思想完全一样，只是指针移动的方向判断反过来。所以核心是“有序”这两个字，递减递增只是表面形式。

1.3 从归并思想看懂这题的底层逻辑

双指针求交集，本质上就是归并排序里“合并两个有序序列”那一步的变体。归并排序合并时，比较两边的值，谁小谁先出；而求交集时，比较两边的值，相等才输出。

所以这道题其实是给后面做归并排序、做多项式相加、做有序序列合并这些题打基础的。PTA把这道题放在前面是有原因的——过了这一关，后面遇到同类型题目，思路迁移会非常顺畅。

我以前刷题时容易忽略“有序”这个条件带来的性质，总想用最通用的方法解决所有问题。后来刷多了才明白，题目给出有序条件，往往就是给你降低复杂度的暗示。如果没有这个条件，双指针法就不成立了，那就得老老实实上哈希。这是算法思维里很关键的一个转变：利用数据的结构特征来简化问题。

2. 核心细节解析与链表操作要点

2.1 带头结点还是不带头结点

这道题我强烈建议使用带头结点的链表。原因很简单：链表为空时，头指针直接指向头结点，头结点的指针域为NULL，处理和返回时不需要额外判断“链表为空时头指针应该是什么”。

ACM类题目和PTA这类在线评测，最怕的就是各种分支边界。带头结点能统一空表和非空表的处理逻辑，让代码少很多if。

定义很简单：

typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;

创建头结点：

LinkList createList() { LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; return head; }

注意：malloc之后一定要检查返回值。虽然做题时内存足够，一般不会失败，但养成习惯总是好的。而且PTA的编译器比较老，有些时候不包含stdlib.h就直接用malloc，会导致隐式声明报错，这个也要留意。

2.2 输入处理：-1是哨兵，不是元素

题目输入是每行若干个整数，以-1表示输入结束。这里有个特别容易踩的坑：-1不是链表节点的一部分，它只是哨兵，用来标识序列结束。

所以建链表时，遇到-1就停，千万不要把-1当作一个值为-1的有效节点加到链表里。

另外，输入每行可能跨多行，不确定在一行里还是两行里，所以读取时要用循环一直读，直到遇到-1为止：

scanf("%d", &x); while (x != -1) { // 将x插入链表 scanf("%d", &x); }

用while循环来处理输入，不要用if。我第一次写的时候用了if，结果第二行数据根本读不进去，程序跑完头结点后面啥也没有，排查了半天才发现是这里的问题。

还有一种做法是读完整行再解析，但PTA的输入用scanf流式处理就够了，毕竟数据量不会大到需要整行读入。

2.3 递减有序链表如何插入新节点

题目给出的序列本身是递减的，比如：25 12 8 3 -1。这串数字已经是排好序的，所以建链表的时候只需要尾插法，一个一个挂在链表末尾就行，不需要额外的排序环节。

尾插法实现很直接：

void appendNode(LinkList tail, int val) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->data = val; p->next = NULL; tail->next = p; tail = p; }

保持一个尾指针tail，始终指向链表的最后一个节点，这样每次插入都是O(1)的复杂度。如果每次从头遍历找尾节点，建链表的复杂度就会变成O(n^2)，虽然这题数据量不一定卡，但坏习惯养成了对后面的题很不利。

输出中要求“按非增序输出”，既然输入时链表本身就是非增序的，那么从头到尾遍历输出即是题目要求的顺序，不需要做任何反转或排序。

2.4 双指针求交集的移动规则

这是整道题的核心。假设A链表当前节点指针为pa，B链表当前节点指针为pb，两个链表都是递减的，也就是从头到尾值越来越小。

比较pa->data和pb->data：

• 若相等：说明是交集元素。输出该值，然后pa和pb同时向后移动。
• 若pa->data > pb->data：说明当前A节点的值比B节点大。因为两个链表都是递减的，B链表中剩下的所有节点值都不会超过pb->data，更不会等于pa->data。所以pa这个节点肯定不是交集元素，把pa向后移。
• 若pa->data < pb->data：反过来，pb这个节点肯定不是交集元素，把pb向后移。

这跟递增序列的处理是对称的。如果链表的顺序换成递增长，那么比较时谁小移谁；现在是递减，谁大移谁。

还有一个容易忽略的点：如果链表中有重复元素怎么办？题目没有明确说明输入中是否含重复元素。稳妥的处理是，输出时遇到重复的交集结果只输出一次。

但这里有个细节：如果A链表中有重复的5，B链表中也有重复的5，双指针比较时会不会重复输出5？比如A中有两个连续的5，B中有一个5。第一次比较时pa指向第一个5，pb指向5，相等，输出一个5，然后pa移到第二个5上，pb移到下一个节点（假设不是5）。这时候pa->data还是5，pb->data小于5，按规则pa后移，循环结束。输出的5只有一个，不会重复。

但还有一种情况：A中两个5，B中两个5。pa和pb都指向5，输出一次，两个指针同时后移，都指着第二个5，又相等，又输出一次。这样就会输出两个5。从严格的集合意义上讲，交集应该只有一个5。

PTA对这道题的数据，实测不处理重复也能过，因为测试数据基本不出现重复元素。但考试时如果严谨一点，可以在输出前判断一下，只有当前值和上一个输出值不同才输出。这样最保险。后续章节我会把这段代码写上，以防万一。

3. 完整代码实现与测试验证

3.1 完整的C语言实现

下面是完整的参考代码。我按模块拆开了，每个函数负责一件事，这样调试起来也清楚。注意语言标准用的是C99，PTA上通常用gcc编译，C99就够用了。

#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 创建带头结点的空链表 LinkList createList() { LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; return head; } // 尾插法建表，输入以-1结束 LinkList readList() { LinkList head = createList(); LinkList tail = head; int x; scanf("%d", &x); while (x != -1) { LNode *node = (LNode*)malloc(sizeof(LNode)); node->data = x; node->next = NULL; tail->next = node; tail = node; scanf("%d", &x); } return head; } // 求两个递减有序链表的交集，使用双指针法 LinkList intersection(LinkList A, LinkList B) { LinkList C = createList(); LinkList tail = C; LNode *pa = A->next; LNode *pb = B->next; // lastVal记录上一个输出的值，用于去重 int lastVal = 0; int hasOutput = 0; while (pa != NULL && pb != NULL) { if (pa->data == pb->data) { // 去重判断：如果上一个输出的值不是当前值，才输出 if (!hasOutput || lastVal != pa->data) { LNode *node = (LNode*)malloc(sizeof(LNode)); node->data = pa->data; node->next = NULL; tail->next = node; tail = node; lastVal = pa->data; hasOutput = 1; } pa = pa->next; pb = pb->next; } else if (pa->data > pb->data) { pa = pa->next; } else { pb = pb->next; } } return C; } void printList(LinkList L) { LinkList p = L->next; if (p == NULL) { printf("NULL\n"); return; } int first = 1; while (p != NULL) { if (!first) { printf(" "); } printf("%d", p->data); first = 0; p = p->next; } printf("\n"); } int main() { LinkList A = readList(); LinkList B = readList(); LinkList C = intersection(A, B); printList(C); return 0; }

3.2 主流程和输出格式说明

整个主流程分四步：

1. 读入链表A
2. 读入链表B
3. 调用intersection函数求交集，得到链表C
4. 遍历链表C并输出，如果C为空则输出NULL

这里的printList函数，我把空格的控制逻辑放到循环内部：用first标志位，第一个元素前面不打印空格，后面的元素打印前先补一个空格。这种写法比“最后一个元素后面不打印空格”的形式要清爽，不用提前判断是不是最后一个节点。很多新手写输出时喜欢在循环里判断“if (p->next == NULL) 不加空格”，这样也行，但要小心循环里提前移动了指针，容易乱了逻辑。

3.3 测试样例与运行结果

我实际跑了三组测试数据，覆盖了正常情况、空链表情况和无交集情况。

第一组，标准样例：

输入： 25 12 8 3 -1 25 12 9 6 3 -1 输出： 25 12 3

第二组，其中一个链表为空：

输入： -1 5 3 1 -1 输出： NULL

第三组，无交集：

输入： 10 8 6 -1 9 7 5 -1 输出： NULL

第四组，带重复元素的测试（这是我自定义的，用来验证去重逻辑）：

输入： 5 5 3 3 1 -1 5 3 3 0 -1 输出： 5 3

多跑几组就能发现，代码的核心逻辑在intersection函数里，其余都是链表常规操作。去重逻辑加上之后，输出结果符合“交集集合”的语义，不会因为重复元素而多输出。

3.4 函数拆分和学习建议

我在代码里刻意把建表、求交集、输出分成三个独立函数，主函数只有几步调用。这样的好处有三个：

• 调试方便。出问题的时候，直接单独测readList，看链表建得对不对，再单独测intersection，不会互相干扰。
• 代码复用。建表和输出这两个函数在其他链表题里也能直接用，比如后面做7-53、7-54等题目，拷贝过来改改就行。
• 符合考试要求。考研复试上机阅卷时，老师看的是代码的整体结构，函数拆得清楚，思路一目了然，得分自然高。

我见过很多同学一上来就全写在main函数里，几十行代码挤在一起，出了bug找半天。不是说不行，但可读性和维护性都差太多了。刷题不光是写出能跑的代码，也要刻意练习代码组织能力。

4. 常见问题与排障技巧实录

4.1 段错误：malloc用错或指针操作越界

这是链表题里最常见的运行时错误。我在做这道题时也遇到过一次段错误，原因是建表时忘了给新节点malloc分配空间，直接把node定义成局部变量，然后让tail->next指向它。局部变量出了作用域就失效了，链表的指针成了野指针，一访问就崩。

正确做法是每次插入节点都必须malloc。还有一个习惯：节点使用完后要free。这题运行完程序就结束了，不free也没事，但如果是做一个长时间运行的程序，不释放内存就会内存泄漏。笔试不会查这个，但面试会问，所以平时就养成好习惯。

4.2 为什么输出一直多一个空格或者少一个空格

输出格式控制看起来是小事，但在线评测对空格和换行卡得非常死。多一个空格、少一个空格都算答案错误。

我第一次用“每个元素后跟空格，直到最后一个不跟”的思路写：

while (p != NULL) { printf("%d", p->data); if (p->next != NULL) printf(" "); p = p->next; }

这个写法本身没错，但容易在p移动之后再去判断p->next，这时候的p已经不是当前节点了。尤其是边输出边移动指针的情况下，很容易判断错。

后来我换成first标志位的方法，简单直接：

int first = 1; while (p != NULL) { if (!first) printf(" "); printf("%d", p->data); first = 0; p = p->next; }

这个思路不管p怎么移动，输出格式都不会乱。推荐大家都用这种方式控制空格。

4.3 循环读入导致死循环

有同学写读入链表时用for循环固定次数，或者用while (scanf("%d", &x))，结果运气好能过，运气不好就卡在读入那里出不来。

正确做法就是读一个数，判断是否为-1，不是就插入，继续读下一个：

scanf("%d", &x); while (x != -1) { // 插入 scanf("%d", &x); }

不要加任何额外的终止条件。题目说了以-1结束，那就只认-1。有些同学为了让程序“更安全”，在循环里加个计数器，比如读够100个就退出，这反而会给特殊数据造成误判。

4.4 求交集时两个指针没有同步移动

双指针法的核心是三个分支：相等、大于、小于。如果代码里少写一个分支，或者把pa和pb的移动写反了，就会出现两种情况：

• 死循环：某个分支没有移动任何指针，循环永远走不下去
• 结果错误：该移动的没移动，该比较的没比较

我在调试时遇到过一次：写第二个分支时，不小心把pa->next写成了pb->next，结果A链表的指针始终不动，程序倒是不死循环，但输出结果完全不对。

排查方法是自己在草稿纸上画两个链表的指针移动过程，走一遍数据流。链表题想不清楚的时候，画图是最好的利器，比硬看代码有效得多。

4.5 关于时间复杂度的思考

有同学问，这题不就是一个20分的题吗，暴力双重循环也能过吗？我也试过。数据量小的时候确实能过，但别侥幸。PTA的测试点通常不止小数据，还有一个大数据的点在后面等着。一旦n和m都到10万级别，双重循环的10^10次比较，在C语言下也要好几秒甚至更久，超时妥妥的。

双指针解法是O(n+m)的，意味着哪怕两个链表各有10万个节点，也只要最多20万次比较，瞬间完成。这20分考查的就是你“有没有意识到有序性质可以优化”的算法思维。

4.6 一个小技巧：输出NULL的条件判断

当交集链表为空时，题目要求输出NULL。这个NULL是字符串“NULL”三个字母，不是空指针。

我见过有些同学直接把空链表头结点打印出来，输出成了乱码。记得printList里要先判断p == NULL，再决定输出NULL还是正常遍历。这一步放在输出函数的开头，不要在主函数里重复判断，这样输出逻辑统一。

5. 从这题延伸出去的学习建议

这道题做完之后，我还顺手练了几个相关的题目，发现思路是可以互相套用的。给大家列几个变形题，自己动手做一遍会有更深的理解：

• 两个有序链表序列的合并：同样是双指针，比较大小，谁小接谁。
• 两个有序链表序列的差集：同样双指针，一个在A不在B时输出。
• 两个有序链表序列的并集：双指针，A的当前值小于B的当前值就输出A并移动A，大于就输出B并移动B，相等就输出其中一个并同时移动。
• 单链表的就地逆置：用头插法逐步反转，这是另一个经典题。

这几个题如果都能不看别人的代码自己写出来，链表这关就算真正过了。数据结构不是靠看会的，是靠一遍一遍写代码、调试、改错堆出来的。

我在刷题的时候还有一个习惯：每道题做完后，把代码压缩到最精简版本，只保留核心逻辑。比如这道题的intersection核心部分，压缩后其实只有十几行。这个过程能帮我提炼出题目的本质，以后遇到类似题一眼就能拆解出解法。这个习惯推荐给你，亲测有效。

最后再说一点，不要因为这道题只有20分就轻视它。PTA的题目集是循序渐进的，前面的基础题没吃透，后面的难题就会越积越多。把每一道20分的题都当成一道完整的算法题来对待，该画图画图，该调试调试，刷题效率反而会更高。