今天遇到个有意思的问题，关于两个单链表找公共结点的。这个题目乍一听感觉没啥难度，但仔细一想，里面的玄机可不少。首先，题目描述得有点模糊，是找第一个公共结点还是所有的公共结点？如果是后者，那可就复杂多了。但根据上下文，应该是第一个公共结点，也就是两个链表第一次交汇的那个点。这时候，我突然想到，这可是数据结构里的经典问题之一，可以用“快慢指针”或者叫“双指针”的技巧来解决，堪称“数据结构”中的小甜甜啊！让我来详细讲讲，顺便带你们去更远的地方看看。

先说说解题思路吧。两个链表长度可能不一样，直接从头开始比较肯定是行不通的，毕竟可能一个链表长，一个链表短，这样没法对齐。那怎么办？很简单，先计算两个链表的长度，找出长度差，然后让长的链表先跑几步，直到两个链表的剩余长度相同。这一步有点像赛跑时为了让跑得慢的人先出发，这样比赛才会公平。这样调整后，再让两个指针同时移动，直到找到相同的位置。

比如，假设链表A有5个节点，链表B有3个节点。两者的长度差是2，那我们就让链表A的指针先移动2步，这样链表A和链表B剩下的节点个数都是3个，此时同时移动两个指针，就能找到第一个公共节点了。如果整个过程中指针都没相遇，那说明两个链表没有公共节点。

那时间复杂度是O(m+n)，其中m和n分别是两个链表的长度。空间复杂度就更不用说了，O(1)，也就是只用到了常数级别的空间。这也符合数据结构中对高效算法的基本要求，毕竟空间换时间已经成了计算机科学中的常见模式。

那我再想想，是不是所有单链表的问题都有类似的解决方式？比如反转链表、合并链表等等。再扩展一点，如果遇到的是数组找公共元素，这方法能不能用？当然可以啊！只不过数组有随机访问的特点，可能不需要指针来回移动，直接用双指针从头开始就行。这又是另一种情况下的优化。所以说，算法思想是相通的，只是数据结构不同，实现方法可能略有不同。

还有一个问题，就是这个方法是不是只能找到第一个公共节点？如果链表有多个公共节点，这种方法只能找到最早的那一个。那如果要找所有的公共节点，就需要做更多的工作，比如记录所有节点，然后找出交集，这就需要更多的空间和时间了。这说明在解决问题时，首先明确题目的要求是很重要的。

最后，我觉得这个问题还可以延伸到更多领域。比如在文件比较中，找两个文件的第一个相同部分，是不是也可以用类似的方法？或者在处理两个字符串时，找第一个相同的子串，这也是一种变体。这说明，掌握这些基础的算法和数据结构，对解决实际问题有着非常重要的意义。

好了，今天就聊到这里。下次再和你们分享更有趣的内容！

文章目录

• 一【题目类别】
• 二【题目来源】
• 三【题目描述】
• 四【解题思路】
• 五【时间频度】
• 六【代码实现】
• 七【程序测试】

一【题目类别】

• 单链表

二【题目来源】

• 本题目选自王道2023考研计算机数据结构复习指导40页中二、综合应用题之08题

三【题目描述】

• 给定两个单链表，编写算法找出两个链表的公共结点。

四【解题思路】

• 首先这个题目描述不是很清楚哈，应该是第一个公共结点，或者题目应该说明只有一个公共结点，否则的话有很多公共结点代码就完全不一样了。整体代码的思路还是比较清晰的，个人感觉类似快慢指针的思想，找出两个单链表的长度差，然后同步两个单链表的长度，最后再同步向前查找，就可以找到第一个公共结点了

五【时间频度】

• 时间复杂度：$O(m+n)$，其中$m、n$分别为两个单链表长度
• 空间复杂度：$O(1)$

六【代码实现】

/*王道2023考研计算机数据结构复习指导40页中二、综合应用题之08题*//*去除警告*/#define _CRT_SECURE_NO_WARNINGS/*引入头文件*/#include#include/*声明定义结点结构体，其中包括数据和指向下一个结点的指针*/typedef struct LNode{int data;struct LNode* next;/*这里就是指向下一个结点的指针，*表示这是一个指针，next是这个指针的名字，struct表示这个指针指向的内容是个结构体*/}Node, *Link;/*这里需要说明Node为结构体的名字，也就是typedef给结构体struct LNode定义了一个别名，这个别名叫Node，而*Link表示一个结构体指针，声明变量的时候要使用malloc开辟内存空间或者指向某一个已经声明的结构体；还有一个区别在于带*定义结构体指针的时候，取内部数据元素的时候要用->，而不带*的知识一个普通的结构体变量，取元素的时候要用.*//*求单链表的长度*/int Length(Link link){int len = 0;Node* p = link->next;while (p != NULL){len++;p = p->next;}return len;}/*本函数的功能为找到两个带头结点的单链表的第一个公共结点*/Link Search_Link_Common(Link L1, Link L2){int len1 = Length(L1);/*求两个单链表的长度*/int len2 = Length(L2);int dist;/*保存两个单链表长度的差值*/Link shortLink, longLink;/*分别指向表长较长和较短的单链表*/if (len1 > len2)/*两表比较长度*/{shortLink = L2->next;longLink = L1->next;dist = len1 - len2;}else{shortLink = L1->next;longLink = L2->next;dist = len2 - len1;}while (dist--)/*注意：0为假，非0为真*/{longLink = longLink->next;/*表长的单链表与表短的单链表进行长度的同步*/}while (longLink != NULL)/*同步寻找公共结点，使用哪个指针都可以，因为已经同步了*/{if (shortLink == longLink)/*找到第一个公共结点*/{return longLink;}else