一种O(n)的办法就是(搞两个指针,一个每次递增一步,一个每次递增两步,如果有环的话两者必然重合,反之亦然):
关于这个解法最形象的比喻就是在操场当中跑步,速度快的会把速度慢的扣圈
可以证明,p2追赶上p1的时候,p1一定还没有走完一遍环路,p2也不会跨越p1多圈才追上
我们可以从p2和p1的位置差距来证明,p2一定会赶上p1但是不会跳过p1的
因为p2每次走2步,而p1走一步,所以他们之间的差距是一步一步的缩小,4,3,2,1,0 到0的时候就重合了
根据这个方式,可以证明,p2每次走三步以上,并不总能加快检测的速度,反而有可能判别不出有环
比如,在环的周长L是偶数的时候,初始p2和p1相差奇数的时候,p2每次走三步,就永远和p1不重合,因为他们之间的差距是: 5, 3 , 1, L-1, L-3
如下代码:
bool check(const node* head)
{
if(head==NULL) return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}
既然能够判断出是否是有环路,那改如何找到这个环路的入口呢?
解法如下: 当p2按照每次2步,p1每次一步的方式走,发现p2和p1重合,确定了单向链表有环路了
接下来,让p2回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当p1和p2再次相遇的时候,就是环路的入口了。
这点可以证明的:
在p2和p1第一次相遇的时候,假定p1走了n步骤,环路的入口是在p步的时候经过的,那么有
p1走的路径: p+c = n; c为p1和p2相交点,距离环路入口的距离
p2走的路径: p+c+k*L = 2*N; L为环路的周长,k是整数
显然,如果从p+c点开始,p1再走n步骤的话,还可以回到p+c这个点
同时p2从头开始走的话,经过n不,也会达到p+c这点
显然在这个步骤当中p1和p2只有前p步骤走的路径不同,所以当p1和p2再次重合的时候,必然是在链表的环路入口点上。
#include <iostream>
#include <stdlib.h>
using namespace std;
class CList {
public:
int nData;
CList * pNext;
} * pRoot = NULL;
const int size = sizeof(CList) / sizeof(int);
int buffer[101*size];
bool Init(int n)
{
pRoot = (CList*)buffer;
if ( n<1 && n>98 ) return false;
CList * pTemp = NULL;
for ( int i=0; i<101; i++ ) {
pTemp = new (buffer+i*size) CList();
pTemp->nData = i;
pTemp->pNext = (CList *)(buffer + (i+1)*size);
};
pTemp->pNext = (CList *) (buffer + n*size);
return true;
}
void ClearCircle(CList * pRoot)
{
CList * p1, * p2;
p1 = p2 = pRoot;
do {
p2 = p2->pNext->pNext;
p1 = p1->pNext;
} while ( p2!=NULL && p1!=p2);
if ( p1 == p2 ) {
p2 = pRoot;
while (1) {
p2 = p2->pNext;
if ( p1->pNext == p2 ) break;
p1 = p1->pNext;
}
p1->pNext = NULL;
}
}
int main(int argc, char *argv[])
{
CList * pList = pRoot;
if (Init(21) )
{
cout << "Before clear:!" << "\r\n";
pList = pRoot;
for ( int i=0; i<104; i++)
{
cout << pList->nData << "\r\n";
pList = pList->pNext;
}
ClearCircle(pRoot);
}
cout << "After clear:" << "\r\n";
pList = pRoot;
while (pList) {
cout << pList->nData << "\r\n";
pList = pList->pNext;
}
return 0;
}
分享到:
相关推荐
**1、判断链表是否有环** **2、寻找环的入口点** **3、计算环的节点数** **4、计算(有环)链表的节点数** **5、找出环中距任意一点最远的节点** **6、判断两个无环链表是否相交** **7、寻找两个链表的相交的节点**
对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中...
判断链表是否有环 反转链表 两个有序链表合并 求链表中间节点 删除倒数第n个节点 两个单链表的公共节点 leetcode建议练习题号: 业界应用 如何实现LRU缓存淘汰算法 stack & queue 栈、队列 知识点 栈 队列 双端队列 ...
栈 链表问题 数字操作问题 快慢指针用处:(1)判断链表是否有环(2)判断入环点(3)获取链表的中间例程 旋转链表贪心策略回溯算法 可移除重复元素 分二查找 位运算 操作数组 回溯解集不能包含重复的组合) 解集不...
2.9 链表环相关问题 2.9.1 链表是否有环 2.9.2 链表环的入口 2.10 改变链表中的元素位置2.11 LRU Cache(设计题) 3. 字符串 3.1 判断字符串是否为回文 3.2 实现strStr() 3.3 字符串转为int(atoi) 3.4 二进制树...
约瑟夫环(循环单链表) 二、应用题 5. 表达式求解 6. 将两个有序线性表合并成一个有序线性表,并去掉重复元素。 7. 设有一个线性单链表,其结点值均为正整数,且按值从大到小链接。试写出一个算法,将该线性...
判断单链表是否有环,快慢指针 单链表有环的情况下,找到环中的第一个节点 合并两个有序链表,保证新的链表也是有序的,递归或者迭代 合并K个有序链表,先写合并2个,然后逐个合并 链表排序,涉及归并排序、快慢指针...
判断单向列表是否有环 206 翻转单向链表 237 删除链表元素 203 删除链表多个元素 206 翻转链表 141 环形链表 2021-05-15: 876 获取链表中间节点 20 判断括号是否成对 2021-05-16: 150后缀表达式 224基本计算器 856...
求图的深度优先或广度优先的生成树(或生成森林)(存储结构为孩子-兄弟链表),并对生成树进行遍历(7、 判断图的连通性,输出连通分量的个数8、 判断图中是否存在环,无向图 9、 给出顶点u和v,判断u到v是否存在...
双向链表也可以有循环表,链表中存在两个环。一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的。 p == p→lLink→rLink == p→rLink→lLink 2.2 栈 栈(Stack)是限定仅在表尾进行插入或删除操作...
对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中...
对任意给定的图(顶点数不小于20,边数不少于30,图的类型可以是有向图、无向图、有向网、无向网),能够输入图的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中...
8、 判断图中是否存在环,无向图5分,有向图10分 9、 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) ...
判断环 ---- 快慢指针 对称翻转 链表常用技巧 递归 定义双变量 let head = p = {}; p.next = l1 这类定义法则 广度遍历 要点: 需要一个队列 queue 每一层遍历时,将当前长度取出来,确保遍历本层节点 循环 长度 次...
判断一个链表是否有环 将数字字符串转成整数 走台阶问题 计算回文字符串 字符串反转 字符串模式匹配 字符串前缀匹配 字典trie匹配 最大连续字符串 字符串压缩 最短路径和 路径总数 最长等差数列 组合硬币数量 最少...
141判断链表有环 双指针,快慢指针 :glowing_star::glowing_star: 14找最长公共前缀 字符串API :glowing_star: 9判断回文数 双指针 :glowing_star: 226 翻转二叉树 二叉树 :glowing_star::glowing_star::glowing_...
5.2l 怎样判断一个程序是用C编译程序环是用C++编译程序编译的? 5.22 预处理指令#pragma有什么作用? 5.23 #line有什么作用? 5.24 标准预定义宏_FILE_有什么作用? 5.25 怎样在程序中打印源文件名? 5.26 ...
首先利用移动速度2的指针和移动速度1的指针,判断是否有环 如果两个指针指向同一个Node, 该Node一定在环内,假设 该Node距离环入口x个Node,环前有a个Node,环内有c个Node,移动了s个步骤: 移动速度1的指针移动了 x...
把堆栈和队列的顺序存储(环队)和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用,如括号匹配、回文判断、事物排队模拟、...
leetcode提交记录怎么看 LeetCode ...链表判断是否有无环. loop / circle 树 其实核心就是遍历. 理解DFS和BFS . (递归+非递归) 进阶篇 , 就是理解了 DFS后, 进行的一些学习吧. 核心是DFS思想这块. 高级