How can one determine whether a singly linked list has a cycle?
第一种方法是从单链表head开始,每遍历一个,就把那个node放在hashset里,走到下一个的时候,把该node放在hashset里查找,如果有相同的,就表示有环,如果走到单链表最后一个node,在hashset里都没有重复的node,就表示没有环。 这种方法需要O(n)的空间和时间。
第二种方法是设置两个指针指向单链表的head, 然后开始遍历,第一个指针走一步,第二个指针走两步,如果没有环,它们会直接走到底,如果有环,这两个指针一定会相遇。
public boolean hasLoop(Node head) {
if (head == null) return false;
//slow pointer
Node sPointer = head.next();
if (sPointer == null) return false;
//fast pointer
Node fPointer = sPointer.next();
while (sPointer != null && fPointer != null) {
if (sPointer == fPointer) return true;
sPointer = sPointer.next();
fPointer = fPointer.next();
if (fPointer != null) {
fPointer = fPointer.next();
}
}
return false;
}
当我们知道这个链表有环了,那么找出起始位置就比较简单。
/* (Step 1) Find the meeting point. This algorithm moves two pointers at
* different speeds: one moves forward by 1 node, the other by 2. They
* must meet (why? Think about two cars driving on a track—the faster car
* will always pass the slower one!). If the loop starts k nodes after the
* start of the list, they will meet at k nodes from the start of the
* loop. */
n1 = n2 = head;
while (TRUE) {
n1 = n1->next;
n2 = n2->next->next;
if (n1 == n2) {
break;
}
}
// Find the start of the loop.
n1 = head;
while (n1 != n2) {
n1 = n1->next;
n2 = n2->next;
}
Now n2 points to the start of the loop.
分析:上面的代码为何能够找到环的起始位置?
假设环的长度是 m, 进入环前经历的node的个数是 k , 那么,假设经过了时间 t,那么速度为2 的指针距离起始点的位置是:k + (2t - k) % m = k + (2t - k) - xm . 同理,速度为1的指针距离起始点的位置是k + (t - k) % m = k + (t - k) - ym。
如果k + (2t - k) - xm =k + (t - k) - ym ,可以得到 t = m (x - y)。 那么当t 最小为m的时候,也就是说,两个指针相聚在 距离 起始点 m - k的环内。换句话说,如果把一个指针移到链表的头部,然后两个指针都以 1 的速度前进,那么它们经过 k 时间后,就可以在环的起始点相遇。
分享到:
相关推荐
8.判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
通过Java实现单链表的操作,包括单链表定义、遍历、置空、判空、插入、删除、反转、中间结点、指定顺序排序、前插、后插、判断单链表是否存在环、环的长度、环的起始结点
代码中包含单链表的常用操作,主要实现以下六个算法: 1.单链表的就地反转 2.链表相交或求公共起始节点 3.求链表倒数第n个节点 ...5.判断链表是否有环 6.将2个递增的链表合并为递减链表 并全部调试通过。
设置窗体相对起始位置.rar 设置窗体相对起始位置.rar
找出一个不全为负的整型数组的最大子段和,并输出起始位置
返回指定字符串的起始位置,在Delphi中的实现方法很简单,使用现有的内置函数就可以,在本示例中我们使用IntToStr就可以轻松获取字符串中指定字符出现的位置,本判断中包括了英文和中文的判断,两种类型都可以使用...
基于802.11a的OFDM符号起始位置估计算法.pdf
当遇到起始点的时候,会认定为出现环(在本文中只是找出了无向图中所有的长度大于等于3的环(长度为1和2的环没有意思),所以在深搜的过程中,当遇到的是起始点的时候,还需要进行判断是否是环),当确定是出现了环...
航迹起始算法中的逻辑航迹起始算法源代码,本算法代码具有很好的起始性能
设置java的环境变量和dos起始位置,
JS获取文本框焦点光标位置、选中起始位置、终止位置、选择内容、兼容IE8,很好的例子!
c++滤除字符串起始位置的空格.cpp
函数作用:一个能计算是否有重复单元的函数...........47 '21.数字金额转中文大写................................48 '22.函数作用:将数字转成英文...........................49 '23.函数作用:人民币大小写转换.......
//请给出一个高效的程序找出2个位置(开始和结束),使从一个A[start]到A[end]的和绝对值最大,并返回这个值(最大值)。 //例 A[5]={2,-1,4,-3,2};该数组最大和的子集合:起始位置为“0”,结束位置为“2” ,最大值为5...
Inception-v4, 在Keras中,起始 v4.起始 Resnet v1和 v2 Keras中的起始使用函数API在Keras中实现 Inception-v4.起始- Resnet-v1和v2体系结构。 本文对这些体系结构的研究,在 "inception-v4.起始resnet和剩余连接对...
在n x n棋盘(有n x n个格点的棋盘)的某个格点上有一个中国象棋马,马走日字。求一条周游棋盘的路径,使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。 用回溯法解决该问题。输入一个正整数n...
取Excel表格有数据单元格的起始行列.rar
新寻找字节集模块(支持起始搜寻位置.rar
真核生物蛋白质生物合成的起始.doc