判断两个单链表相交
判断 2 个单链表是否相交,是一个老生常谈但又极具思考性的面试题,本节就在读者已经掌握单链表及其基本操作的基础上,就此问题给大家做深入地讲解。
首先,读者要搞清楚“相交”的含义。所谓相交,是指有公共的部分,而 2 个单链表相交,则意味着它们有公共的节点,公共节点的数量可以是 1 个或者多个。
通过前面的学习我们知道,单链表是线性表的一种,如果我们将 2 个单链表看做 2 条线段的话,图 1 模拟了 2 条线段相交的所有可能情况。
图 1 链表相交
注意,结合“单链表中每个节点有且仅有 1 个指针域”的特性,如 1 所示的这 3 种情况中,只有第 2 种情况符合单链表的特性,另外 2 种情况则破坏了此特性。经过以上的分析,本节要验证 2 个单链表是否相交,实际上等同于判断 2 个单链表是否和图 1② 所示的存储结构相同。
判断 2 个单链表(下文分别称它们为链表 1 和链表 2 )是否相交,常用的方法有如下几种。
1) 分别遍历链表 1 和链表 2,对于链表 1 中的每个节点,依次和链表 2 中的各节点进行比对,查看它们的存储地址是否相同,如果相同,则表明它们相交;反之,如果链表 1 中各节点的存储地址,和链表 2 中的各个节点都不相同,则表明它们不相交。
2) 实际上,第 1 种实现方案还可以进一步优化。结合图 1②,2 个单链表相交有一个必然结果,即这 2 个链表的最后一个节点必定相同;反之,如果 2 个链表不相交,则这 2 个链表的最后一个节点必定不相同。
由此,可以对以上实现代码进行优化:
3) 针对第 1 种实现方案的优化,除了第 2 种方式,还有一种思想。
假设 L1 和 L 2 相交,则两个链表中相交部分节点的数量一定是相等的。如图 2 所示:
图 2 两个链表相交
可以看到,L1 和 L2 相交,绿色部分节点为 L1 和 L2 链表的相交部分。
也就是说,如果 2 个链表相交,那么它们相交部分所包含的节点个数一定相等。在此基础上,我们可以这样优化第 1 种实现方案,以图 2 中的 L1 和 L2 为例,从 L1 尾部选取和 L2 链表等长度的一个子链表(也也就是图 3 中的 temp 子链表),同时遍历 temp 和 L2 链表,依次判断 2 个遍历节点是否相同,如果相同则表明 L1 和 L2 相交;反之则不相交。
图 3 在较长链表中找到和较短链表等长度的子链表
此实现方案的实现代码如下:
从另一个角度比较这 3 种方案,第 1 种和 第 3 种在判断“2 个链表是否相交”的同时,还能找到它们相交的交点,而第 2 种实现方案则不具备这个功能。
首先,读者要搞清楚“相交”的含义。所谓相交,是指有公共的部分,而 2 个单链表相交,则意味着它们有公共的节点,公共节点的数量可以是 1 个或者多个。
通过前面的学习我们知道,单链表是线性表的一种,如果我们将 2 个单链表看做 2 条线段的话,图 1 模拟了 2 条线段相交的所有可能情况。
图 1 链表相交
注意,结合“单链表中每个节点有且仅有 1 个指针域”的特性,如 1 所示的这 3 种情况中,只有第 2 种情况符合单链表的特性,另外 2 种情况则破坏了此特性。经过以上的分析,本节要验证 2 个单链表是否相交,实际上等同于判断 2 个单链表是否和图 1② 所示的存储结构相同。
判断 2 个单链表(下文分别称它们为链表 1 和链表 2 )是否相交,常用的方法有如下几种。
1) 分别遍历链表 1 和链表 2,对于链表 1 中的每个节点,依次和链表 2 中的各节点进行比对,查看它们的存储地址是否相同,如果相同,则表明它们相交;反之,如果链表 1 中各节点的存储地址,和链表 2 中的各个节点都不相同,则表明它们不相交。
仍以前面章节中构建的单链表为例:注意,此方法中比较的是节点的存储地址,而非数据域中存储的元素。原因很简单,数据域中存储元素值相同,并不是 2 个单链表相交的充分条件,因为 2 个不相交的链表中很可能存有相同的元素。
typedef struct Link { char elem; //代表数据域 struct Link * next; //代表指针域,指向直接后继元素 }link; //link为节点名,每个节点都是一个 link 结构体在此基础上,判断 2 个单链表是否相交的实现代码为:
//自定义的 bool 类型 typedef enum bool { False = 0, True = 1 }bool; //L1 和 L2 为 2 个单链表,函数返回 True 表示链表相交,返回 False 表示不相交 bool LinkIntersect(link * L1, link * L2) { link * p1 = L1; link * p2 = L2; //逐个遍历 L1 链表中的各个节点 while (p1) { //遍历 L2 链表,针对每个 p1,依次和 p2 所指节点做比较 while (p2) { //p1、p2 中记录的就是各个节点的存储地址,直接比较即可 if (p1 == p2) { return True; } p2 = p2->next; } p1 = p1->next; } return False; }通过分析 LinkIntersect() 函数的实现过程不难得知,无论 2 个链表是否相交,此实现方式的时间复杂度为
O(n2)
。
有关时间复杂度的计算过程,读者可阅读《时间复杂度和空间复杂度》一节,这里不再做过多赘述。
2) 实际上,第 1 种实现方案还可以进一步优化。结合图 1②,2 个单链表相交有一个必然结果,即这 2 个链表的最后一个节点必定相同;反之,如果 2 个链表不相交,则这 2 个链表的最后一个节点必定不相同。
由此,可以对以上实现代码进行优化:
//L1 和 L2 为 2 个单链表,函数返回 True 表示链表相交,返回 False 表示不相交 bool LinkIntersect(link * L1, link * L2) { link * p1 = L1; link * p2 = L2; //找到 L1 链表中的最后一个节点 while (p1->next) { p1 = p1->next; } //找到 L2 链表中的最后一个节点 while (p2->next) { p2 = p2->next; } //判断 L1 和 L2 链表最后一个节点是否相同 if (p1 == p2) { return True; } return False; }显然经过优化,该函数的时间复杂度就缩小为
O(n)
。3) 针对第 1 种实现方案的优化,除了第 2 种方式,还有一种思想。
假设 L1 和 L 2 相交,则两个链表中相交部分节点的数量一定是相等的。如图 2 所示:
图 2 两个链表相交
可以看到,L1 和 L2 相交,绿色部分节点为 L1 和 L2 链表的相交部分。
也就是说,如果 2 个链表相交,那么它们相交部分所包含的节点个数一定相等。在此基础上,我们可以这样优化第 1 种实现方案,以图 2 中的 L1 和 L2 为例,从 L1 尾部选取和 L2 链表等长度的一个子链表(也也就是图 3 中的 temp 子链表),同时遍历 temp 和 L2 链表,依次判断 2 个遍历节点是否相同,如果相同则表明 L1 和 L2 相交;反之则不相交。
图 3 在较长链表中找到和较短链表等长度的子链表
//L1 和 L2 为 2 个单链表,函数返回 True 表示链表相交,返回 False 表示不相交 bool LinkIntersect(link * L1, link * L2) { link * plong = L1; link * pshort = L2; link * temp = NULL; int num1 = 0, num2 = 0, step = 0; //得到 L1 的长度 while (plong) { num1++; plong = plong->next; } //得到 L2 的长度 while (pshort) { num2++; pshort = pshort->next; } //重置plong和pshort,使plong代表较长的链表,pshort代表较短的链表 plong = L1; pshort = L2; step = num1 - num2; if (num1 < num2) { plong = L2; pshort = L1; step = num2 = num1; } //在plong链表中找到和pshort等长度的子链表 temp = plong; while (step) { temp = temp->next; step--; } //逐个比较temp和pshort链表中的节点是否相同 while (temp && pshort) { if (temp == pshort) { return True; } temp = temp->next; pshort = pshort->next; } return False; }相比第 2 种方案,此方法的实现逻辑虽然复杂,但优点是,该方法可以找到 2 个单链表相交的交点(也就是相交时的第一个节点),也就是使 LinkIntersect() 函数返回 True 时的 temp 指针指向的那个节点。另外,此方案的时间复杂度也为
O(n)
。
总结
总的来说,本节讲解了 3 种“判断 2 个链表是否相交”的方法,其中第 2、3 种方案的时间复杂度都比第 1 种要小。从另一个角度比较这 3 种方案,第 1 种和 第 3 种在判断“2 个链表是否相交”的同时,还能找到它们相交的交点,而第 2 种实现方案则不具备这个功能。
如果读者想实现“判断 2 个链表是否相交,如果相加找到交点”这样的功能,只需对第 1、3 种方案的实现代码做略微调整即可。由于很简单,读者可自行尝试实现。
所有教程
- C语言入门
- C语言编译器
- C语言项目案例
- 数据结构
- C++
- STL
- C++11
- socket
- GCC
- GDB
- Makefile
- OpenCV
- Qt教程
- Unity 3D
- UE4
- 游戏引擎
- Python
- Python并发编程
- TensorFlow
- Django
- NumPy
- Linux
- Shell
- Java教程
- 设计模式
- Java Swing
- Servlet
- JSP教程
- Struts2
- Maven
- Spring
- Spring MVC
- Spring Boot
- Spring Cloud
- Hibernate
- Mybatis
- MySQL教程
- MySQL函数
- NoSQL
- Redis
- MongoDB
- HBase
- Go语言
- C#
- MATLAB
- JavaScript
- Bootstrap
- HTML
- CSS教程
- PHP
- 汇编语言
- TCP/IP
- vi命令
- Android教程
- 区块链
- Docker
- 大数据
- 云计算