大家好，今天Win10系统之家小编给大家分享「单链表如何判断有环」的知识，如果能碰巧解决你现在面临的问题，记得收藏本站或分享给你的好友们哟~，现在开始吧！

1.判断单链表是否有环

　　方法一：直接法
直接判断第一个链表的每个结点是否在第二个链表中，时间复杂度为o(len1*len2)，耗时很大
方法二：利用计数
如 果 两个链表相交，则两个链表就会有共同的结点；而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共 同的结点。这个方法的时间复杂度为：o(max(len1+len2)；但同时还得增加o(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加 了存储空间。
以链表节点地址为值，遍历第一个链表，使用hash保存所有节点地址值，结束条件为到最后一个节点（无环）或hash中该地址值已经存在（有环）。
再遍历第二个链表，判断节点地址值是否已经存在于上面创建的hash表中。
这个方面可以解决题目中的所有情况，时间复杂度为o(m+n)，m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型，假设链表都是在堆中动态创建的，可以使用堆的起始地址作为偏移量，以地址减去这个偏移量作为hash函数
方法三
两个没有环的链表相交于一节点，则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交，则最后一个结点一定是共有的，则只需要判断最后一个结点是否相同即可。时间复杂度为o(len1+len2)。对于相交的第一个结点，则可求出两个链表的长度，然后用长的减去短的得到一个差值 k，然后让长的链表先遍历k个结点，然后两个链表再开始比较。还可以这样：其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个

2.Java判断单链表是否有环的两种实现方法

　　方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 ， 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。
方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。
这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。
方法三：首先创建两个指针1和2（在Java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。
此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

3.判断单链表中是否有环，找到环的入口节点

　　1.判断链表是否有环
设置两个指针slow和fast,初始值均指向链表头,slow每次向前走一步,而fast每次向前走两步.
如果链表有环,则fast先进入环里,而slow后进入环里,两个指针在环中必定相遇.
如果slow与fast没有相遇,fast遍历到链表的尾部,则表示链表没有环.
2.链表有环,确定环的入口点
设置slow指针指向链表头,fast指向相遇点,每次两个指针都是只走一步,两个指针必定相遇,
则相遇第一点为环入口点.
( 为什么 两个指针相遇的地方就是环入口点?
 先从"判断链表是否有环"的那种情况说起.
 假设从链表头到环入口点的距离是x, 在环里两个指针相遇的那点与环入口点的距离是w,
 fast指针在环里走了n圈才与slow相遇,环的长度是L,那么,
 slow指针在相遇时走过的距离是 x + w
 fast指针走过的距离是 x + w + n*L
 因为slow每次向前走一步,而fast每次向前走两步,有如下等式:
 2 * (x + w) = x + w + n*L
 化简得到: x + w = n*L
 也就是 x = n*L - w [等式1]
 假设相遇的时候,fast在环内只走了一圈,n=1,代入[等式1],得到 x = L - w
 现在,slow从链表头开始走,fast继续从相遇点开始走,两个指针都只走一步,
 那么,slow走了x,而fast走了(L - w),必定相遇,而且刚好在环入口点.
 假设相遇的时候,fast在环内走了超过一圈,那么[等式1]可以写为:
 x = (n-1)*L + (L- w)
 那么,slow走了x,而fast走了(n-1)圈后,再走(L - w),必定相遇,而且刚好在环入口点. )
3.计算环长
在环的入口点设置一个指针和一个计数器,让这个指针在环里面走,每走一步,计数器就加1,
当这个指针回到环的入口点的时候,计数器的值就是环长.
测试结果:
链表1:
10 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40 50 20 30 40 ......
有环, 环入口点是: 20
环长是: 4
链表2:
1 2 3 4 5
链表没有环
//C语言测试程序
#include 
#include 
typedef struct Node
{
 int data;
 struct Node *next;
}Node,*LinkList;
//创建链表(有"环")
LinkList CreateLinkWithLoop()
{
 LinkList head; //链表头
 Node *newNode; //新结点
 Node *ptr; //指向当前结点
 Node *pEntry; //指向"环"的入口
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=10;
 newNode->next=NULL;
 head=newNode; //设置链表头
 ptr=newNode;
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=20;
 newNode->next=NULL;
 ptr->next=newNode;
 ptr=newNode;
 pEntry=newNode; //指向"环"的入口
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=30;
 newNode->next=NULL;
 ptr->next=newNode;
 ptr=newNode;
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=40;
 newNode->next=NULL;
 ptr->next=newNode;
 ptr=newNode;
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=50;
 newNode->next=pEntry; //产生"环"
 ptr->next=newNode;
 ptr=newNode;
 return head;
}
//创建链表(没有"环")
LinkList CreateLink()
{
 LinkList head; //链表头
 Node *newNode; //新结点
 Node *ptr; //指向当前结点
 int i;
 newNode=(Node *)malloc(sizeof(Node));
 newNode->data=1;
 newNode->next=NULL;
 head=newNode; //设置链表头
 ptr=newNode;
 for(i=2;i<=5;i++) {="" newnode="(Node *)malloc(sizeof(Node));" newnode-="">data=i;
 newNode->next=NULL;
 ptr->next=newNode;
 ptr=newNode;
 }
 return head;
}
//打印链表
void PrintLink(LinkList head)
{
 LinkList ptr;
 int nCount=0;
 ptr=head;
 while(ptr!=NULL)
 {
 printf("%d ",ptr->data);
 ptr=ptr->next;
 nCount++;
 if(nCount>=20)
 {
 printf("......");
 break;
 }
 }
 printf("\n");
}
//判断链表是否有"环",确定"环"的入口点
LinkList CheckLinkLoop(LinkList head)
{
 LinkList fast;
 LinkList slow;
 int isLoop=0;
 fast=head;
 slow=head;
 while(fast != NULL && fast->next != NULL)
 {
 //fast每次走两步,slow每次走一步
 //当两个指针相等时,表示链表有"环"
 slow=slow->next;
 fast=fast->next->next;
 if(fast == slow)
 {
 isLoop=1; //1=有环, 0=没有环
 break;
 }
 }
 if(isLoop==1) //有"环"时
 {
 //slow指向链表头,fast指向相遇点,两个指针每次都只走一步
 //当两个指针第一次相等时,就是环入口点
 slow=head;
 while(slow != fast)
 {
 slow=slow->next;
 fast=fast->next;
 }
 return slow;
 }
 else //没有"环"
 {
 return NULL;
 }
}
//计算环长
int GetLoopSize(LinkList entryNode)
{
 LinkList ptr;
 int nCount=0;
 ptr=entryNode->next;
 nCount++;
 while(ptr!=entryNode)
 {
 nCount++;
 ptr=ptr->next;
 }
 return nCount;
}
int main()
{
 LinkList head_1;
 LinkList head_2;
 LinkList ret_1;
 LinkList ret_2;
 int loopSize_1;
 int loopSize_2;
 head_1=CreateLinkWithLoop(); //创建链表(有"环")
 printf("链表1:\n");
 PrintLink(head_1); //打印链表
 ret_1=CheckLinkLoop(head_1);
 if(ret_1!=NULL)
 {
 printf("有环, 环入口点是: %d\n",ret_1->data);
 loopSize_1=GetLoopSize(ret_1);
 printf("环长是: %d\n",loopSize_1);
 }
 else
 {
 printf("链表没有环\n");
 }
 head_2=CreateLink(); //创建链表(没有"环")
 printf("\n链表2:\n");
 PrintLink(head_2); //打印链表
 ret_2=CheckLinkLoop(head_2);
 if(ret_2 != NULL)
 {
 printf("有环, 环入口点是: %d\n",ret_2->data);
 loopSize_2=GetLoopSize(ret_2);
 printf("环长是: %d\n",loopSize_2);
 }
 else
 {
 printf("链表没有环\n");
 }
 return 0;
}</=5;i++)>

4.判断单链表有没有环的算法中，至少需要几个指针

　　算法的思想是设定两个指针p, q，其中p每次向前移动一步，q每次向前移动两步。那么如果单链表存在环，则p和q相遇；否则q将首先遇到null。
这里主要理解一个问题，就是为什么当单链表存在环时，p和q一定会相遇呢？
　　
假定单链表的长度为n，并且该单链表是环状的，那么第i次迭代时，p指向元素i mod n，q指向2i mod n。因此当i≡2i(mod n)时，p与q相遇。而i≡2i(mod n) => (2i - i) mod n = 0 => i mod n = 0 => 当i=n时，p与q相遇。这里一个简单的理解是，p和q同时在操场跑步，其中q的速度是p的两倍，当他们两个同时出发时，p跑一圈到达起点，而q此时也刚 好跑完两圈到达起点。
那么当p与q起点不同呢？假定第i次迭代时p指向元素i mod n，q指向k+2i mod n，其中0<k<n。那么i≡(2i+k)(mod n) => (i+k) mod n = 0 => 当i=n-k时，p与q相遇。
　　解决方案：
　　推广：
　　1. 如果两个指针的速度不一样，比如p，q，( 0<p<q)二者满足什么样的关系，可以使得两者肯定交与一个节点？
　　   Sp(i) = pi
　　   Sq(i) = k + qi
　　   如果两个要相交于一个节点，则 Sp(i) = Sq(i) =>  (pi) mod n = ( k+ qi ) mod n =>[ (q -p)i + k ]  mod n =0
　　   =>  (q-p)i + k  = Nn [N 为自然数]
　　   =>  i = (Nn -k) /(p-q)
　　   i取自然数，则当 p，q满足上面等式 即 存在一个自然数N，可以满足Nn -k 是 p - q 的倍数时，保证两者相交。
　　   特例：如果q 是p 的步长的两倍，都从同一个起点开始，即 q = 2p , k =0, 那么等式变为： Nn=i： 即可以理解为，当第i次迭代时，i是圈的整数倍时，两者都可以交，交点就是为起点。
　　2.如何判断单链表的环的长度？
　　   这个比较简单，知道q 已经进入到环里，保存该位置。然后由该位置遍历，当再次碰到该q 位置即可，所迭代的次数就是环的长度。
　　3. 如何找到链表中第一个在环里的节点？
　　   假设链表长度是L，前半部分长度为k-1，那么第一个再环里的节点是k，环的长度是 n， 那么当q=2p时， 什么时候第一次相交呢？当q指针走到第k个节点时，q指针已经在环的第 k mod n 的位置。即p和q 相差k个元素，从不同的起点开始，则相交的位置为 n-k
　　从图上可以明显看到，当p从交点的位置（n-k) ,向前遍历k个节点就到到达环的第一个几点，节点k.
　　算法就很简单： 一个指针从p和q 中的第一次相交的位置起（n-k)，另外一个指针从链表头开始遍历，其交点就是链表中第一个在环里的交点。
　　4. 如果判断两个单链表有交？第一个交点在哪里？
　　   这个问题画出图，就可以很容易转化为前面的题目。
　　  将其中一个链表中的尾节点与头节点联系起来，则很容发现问题转化为问题3，求有环的链表的第一个在环里的节点。

5.判断链表是否有环 找到环的入口节点

　　实际上这里包含两个问题：
　　(h2)问题一：如何判断给定的链表是以NULL结尾，还是形成了一个环？
　　思路分析：
　　蛮力法：从表头开始遍历，针对每个节点均检查是否存在它之后的某个节点的后继指针指向该节点，如果存在则说明该链表存在环。如果一直遍历到表尾节点都未发现这种节点，则说明该链表不存在环。很显然这种算法是一种效率很差的算法，因此不考虑使用
　　使用散列表（哈希表）：从表头开始逐个遍历链表中的每个节点，并检查其是否已经存在散列表中。如果存在则说明已经访问过该节点了，也就是存在环；如果一直到表尾都没有出现已经访问过的节点，则说明该链表不存在环。时间复杂度：O(n)
　　Floyd环判定算法：使用两个在链表中具有不同移动速度的指针（如：fastNode每次移动两个节点，slowNode每次移动一个节点），两个指针同时从表头开始移动，如果在某一时刻它们相遇了，则表明该链表存在环。原因很简单：快速移动指针和慢速移动指针将会指向同一位置的唯一可能情况就是整个或者部分链表是一个环
　　(h2)
(h2)问题二：如果链表中存在环，找到环的入口节点
　　思路分析：
　　首先使用Floyd环判定算法判断一个链表是否存在环。在找到环之后，将slowNode重新设置为表头节点，接下来slowNode和fastNode每次分别移动一个节点，当它们再次相遇时即为环的起始节点
　　时间复杂度：O(n)
　　证明：
　　设飞环长度为：C1，整个环的长度为：C2，两个指针相遇时走过的环中的弧长为：C3
　　第一次相遇时：
　　Sslow = C1 + C3
　　Sfast = C1 + C2 + C3
　　且：Sfast = 2Sslow
　　则：C1 = C2 – C3
　　当slowNode重置为表头节点，两个指针只需要分别移动C1即可第二次相遇：
　　slowNode移动长度：C1，此时slowNode的位置是环的开始节点
　　fastNode移动长度：C1 = C2 – C3，也就是说fastNode此时的位置是：初始位置C3 + C2 – C3 = C2，也就是说fastNode此时刚好移动到环的开始节点，二者相遇
　　
　　(h2)示例代码：
　　定义一个单向链表的单个节点：
　　package cn.zifangsky.linkedlist;
/**
 * 单链表的定义
 * 
 * @author zifangsky
 *
 */
public class SinglyNode {
 private int data; // 数据
 private SinglyNode next; // 该节点的下个节点
 public SinglyNode(int data) {
 this.data = data;
 }
 public SinglyNode(int data, SinglyNode next) {
 this.data = data;
 this.next = next;
 }
 public int getData() {
 return data;
 }
 public void setData(int data) {
 this.data = data;
 }
 public SinglyNode getNext() {
 return next;
 }
 public void setNext(SinglyNode next) {
 this.next = next;
 }
 @Override
 public String toString() {
 return "SinglyNode [data=" + data + "]";
 }
}
package cn.zifangsky.linkedlist.questions;
import org.junit.Test;
import cn.zifangsky.linkedlist.SinglyNode;
/**
 * 判断给定的链表是以NULL结尾，还是形成了一个环？如果链表中存在环，则找到环的起始节点
 * @author zifangsky
 *
 */
public class Question3 {
 
 /**
  * 在找到环之后，将slowNode重新设置为表头节点，接下来slowNode和fastNode每次分别移动一个节点，
  * 当它们再次相遇时即为环的起始节点
  * 
  * @时间复杂度 O(n)
  * @param headNode
  * @return
  */
 public SinglyNode findLoopStartNode(SinglyNode headNode){
 SinglyNode fastNode=headNode,slowNode=headNode;
 boolean loopExists = false; //是否存在环的标识
 
 while(slowNode.getNext() != null && fastNode.getNext() != null && fastNode.getNext().getNext() != null){
 slowNode = slowNode.getNext();
 fastNode = fastNode.getNext().getNext();
 
 if(slowNode == fastNode){
 loopExists = true;
 break;
 }
 }
 
 //如果存在环，则slowNode回到表头
 if(loopExists){
 slowNode = headNode;
 while(slowNode != fastNode){
 slowNode = slowNode.getNext();
 fastNode = fastNode.getNext();
 }
 return fastNode;
 
 }
 return null;
 }
 
 @Test
 public void testMethods(){
 SinglyNode headNode1 = new SinglyNode(11);
 
 SinglyNode currentNode = headNode1;
 for(int i=2;i<=5;i++){
 SinglyNode tmpNode = new SinglyNode(11 * i);
 currentNode.setNext(tmpNode);
 currentNode = tmpNode;
 }
 
 //链表headNode2，人为构造了一个环
 SinglyNode headNode2 = new SinglyNode(11);
 SinglyNode ringStartNode = null;
 currentNode = headNode2;
 for(int i=2;i<=8;i++){
 SinglyNode tmpNode = new SinglyNode(11 * i);
 currentNode.setNext(tmpNode);
 currentNode = tmpNode;
 if(i == 3){
 ringStartNode = tmpNode;
 }else if(i == 8){
 tmpNode.setNext(ringStartNode);
 }
 }
 System.out.println("链表headNode1的环的起始节点：" + findLoopStartNode(headNode1)
 + "；链表headNode2的环的起始节点：" + findLoopStartNode(headNode2));
 }
 
}
　　最后测试用例的输出如下：
　　链表headNode1的环的起始节点：null；链表headNode2的环的起始节点：SinglyNode [data=33]
　　注：上面代码中只给出了经典的Floyd环判定算法的实现方式，其他实现方式可以自行网上搜索或者参考我博客上的示例
　　（PS：纯手打，望采纳！）

以上就是关于「单链表如何判断有环」的全部内容，本文讲解到这里啦，希望对大家有所帮助。如果你还想了解更多这方面的信息，记得收藏关注本站~

【文②章♀来自Win10系统之家，转载请联系！】