判断链表中有环
《循环链表》一节,给大家详细地介绍了循环链表。在此基础上,本节带领大家讨论一个问题:如何判断一个单链表中有环?
注意,有环链表并不一定就是循环链表。循环链表指的是“首尾相连”的单链表,而有环链表则指的是单链表中存在一个循环子链表,如图 1 所示。
图 1 有环链表示意图
图 1 所示就是一个有环链表,但并不是循环链表。
那么,如果给定一个单链表,如何判断其是否为有环链表呢?常用的判断方法有如下 2 种。
1) 最直接的实现思想就是:从给定链表的第一个节点开始遍历,每遍历至一个节点,都将其和所有的前驱节点进行比对,如果为同一个节点,则表明当前链表中有环;反之,如果遍历至链表最后一个节点,仍未找到相同的节点,则证明该链表中无环。
2) 相比上一种实现方案,这里介绍一种时间复杂度为 O(n) 的算法。
该算法的实现思想需要借助一个论点,即在一个链表中,如果 2 个指针(假设为 H1 和 H2)都从表头开始遍历链表,其中 H1 每次移动 2 个节点的长度(H1 = H1->next->next),而 H2 每次移动 1 个节点的长度(H2 = H2->next),如果该链表为有环链表,则 H1、H2 最终必定会相等;反之,如果该链表中无环,则 H1、H2 永远不会相遇。
注意,有环链表并不一定就是循环链表。循环链表指的是“首尾相连”的单链表,而有环链表则指的是单链表中存在一个循环子链表,如图 1 所示。
图 1 有环链表示意图
图 1 所示就是一个有环链表,但并不是循环链表。
那么,如果给定一个单链表,如何判断其是否为有环链表呢?常用的判断方法有如下 2 种。
1) 最直接的实现思想就是:从给定链表的第一个节点开始遍历,每遍历至一个节点,都将其和所有的前驱节点进行比对,如果为同一个节点,则表明当前链表中有环;反之,如果遍历至链表最后一个节点,仍未找到相同的节点,则证明该链表中无环。
基于上面的实现思想,下面设计了一个相应的实现函数:注意,如果一个单链表为有环链表,基于单链表中各节点有且仅有 1 个指针域的特性,则势必该链表是没有尾结点的(如图 1 所示)。换句话说,有环链表的遍历过程是无法自行结束的,需要使用 break 语句手动结束遍历。
//自定义 bool 类型 typedef enum bool { False=0, True=1 }bool; // H 为链表的表头 bool HaveRing(link * H) { link * Htemp = H; //存储所遍历节点所有前驱节点的存储地址,64位环境下地址占 8 个字节,所以这里用 long long 类型 long long addr[20] = { 0 }; int length = 0, i = 0; //逐个遍历链表中各个节点 while (Htemp) { //依次将 Htemp 和 addr 数组中记录的已遍历的地址进行比对 for (i = 0; i < length; i++) { //如果比对成功,则证明有环 if (Htemp == addr[i]) { return True; } } //比对不成功,则记录 Htemp 节点的存储地址 addr[length] = Htemp; length++; Htemp = Htemp->next; } return False; }如上所示,当函数的返回值为 True,表示该链表有环;反之若函数返回值为 False,表明链表中无环。显然,此实现方案的时间复杂度为
O(n2)
。2) 相比上一种实现方案,这里介绍一种时间复杂度为 O(n) 的算法。
该算法的实现思想需要借助一个论点,即在一个链表中,如果 2 个指针(假设为 H1 和 H2)都从表头开始遍历链表,其中 H1 每次移动 2 个节点的长度(H1 = H1->next->next),而 H2 每次移动 1 个节点的长度(H2 = H2->next),如果该链表为有环链表,则 H1、H2 最终必定会相等;反之,如果该链表中无环,则 H1、H2 永远不会相遇。
基于以上这个结论,我们可以轻松编写出对应的实现代码:有关在有环链表中 H1 和 H2 必定会相遇的结论,假设有环链表中的环包含 n 个节点,则第一次遍历,H1 和 H2 相差 1 个节点;第二次遍历,H1 和 H2 相差 2 个节点;第三次遍历,H1 和 H2 相差 3 个节点...,最终经过多次遍历,H1 和 H2 会相差 n-1 个节点,此时就会在环中重合,此时 H1 和 H2 相等。
//H为链表的表头,该函数会返回一个枚举的 bool 类型数据 bool HaveRing(link * H) { link * H1 = H->next; link * H2 = H; while (H1) { if (H1 == H2) { //链表中有环 return True; } else { H1 = H1->next; if (!H1) { //链表中无环 return False; } else { H1 = H1->next; H2 = H2->next; } } } //链表中无环 return False; }和上一种实现代码一样,当函数返回 False 时,表明当前链表中无环;反之若返回 True,则表明该链表为有环链表。和第一种算法相比,本算法的时间复杂度为 O(n)。
所有教程
- 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
- 大数据
- 云计算