判断单链表中是否有环,找到环的入口节点
发布网友
发布时间：2022-04-14 20:53
共2个回答
懂视网
时间：2022-04-15 01:14
给定一个有环链表，实现以算法返回环路的开头结点。 有环链表的定义 在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。 示例 输入：A-B-C-D-E-C(C节点出现两次) 输出：C 分析 ： 1，快慢指针法判断链表是否有环 fast每次前移两步，
给定一个有环链表，实现以算法返回环路的开头结点。
有环链表的定义
在链表中某个节点的next元素指向它前面出现过的节点，则表明该链表存在环路。
示例
输入：A->B->C->D->E->C(C节点出现两次)
输出：C
分析：
1，快慢指针法判断链表是否有环
fast每次前移两步，slow每次前移一步，两指针若能相遇，则有环，否则没有环。
2，假设链表头到环头移动k步，slow指向环头的时候，fast移动了2*k步，此时两者相距k步，也可以认为快指针再过m*size-k步之后追上慢指针。当两者相遇的时候，则慢指针距离环头还有k步。因为此时不知道k的具体大小，但是知道k是链表头到环头的步数，让fast指向链表头，之后快慢指针每次往后移动一步，两者相遇的地方就是环头。
package test;
public class FindLoopStart {
public Node findLoopStart(Node head){
Node fast = head;
Node slow = head;
while(fast!=null || fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
break;
}
//没有环则返回null
if(fast==null || fast.next==null)
return null;
//相遇之后，slow节点再走k步达到环开头
//此时，并不知道k的具体值，但是知道k是从链表开头到环头的步数
//于是，让fast指向链表头，每次往后移一步，则再次相遇的时候，走的步数就是k
//则相遇地点就是环的开头
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
热心网友
时间：2022-04-14 22:22
设置两个指针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 <stdio.h>
#include <stdlib.h>
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;
}
