- 首页 > it技术 > >
问题：如何判断单链表是否有环？如何找到环的起始点？如何知道环的长度。
方法：使用快慢指针法，即快指针每次移动两个节点，慢指针每次移动一个节点
文章图片
（1）判断是否有环
如图所示，假设有两个节点fast，slow分别指向链表头，即图中的节点1所在的地址。然后令
slow = slow->next;
fast = fast->next->next;
然后循环执行知道slow等于fast时，即可推断出环的存在。注意循环条件为fast != NULL && fast->next != NULL。 【链表的环问题】
代码如下所示：
#include
#include typedef struct node
{
int data;
struct node * next;
}Node;
Node * get_circle_link(int length, int local)
{
Node *temp = NULL;
Node *phead = NULL;
Node *tail = NULL;
int i;
//创建单链表
for (i = 0;
i < length;
i++)
{
temp = (Node *)malloc(sizeof(Node));
temp->next = NULL;
temp->data = https://www.it610.com/article/length - i;
if (phead == NULL)
{
tail = temp;
} temp->next = phead;
phead = temp;
}//形成环
for (temp = phead, i =1;
i < local;
i++)
{
temp = temp->next;
}
tail->next = temp;
return phead;
}void link_print(Node *temp)
{
while (temp != NULL)
{
printf("%p:%d\t",temp,temp->data);
temp = temp->next;
getchar();
}
}//利用快慢指针判断链表是否有环
int get_circle_local(Node *phead)
{
Node * fast = phead;
Node * slow = phead;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
//fast一次跳两个节点
slow = slow->next;
//slow一次跳一个节点 if (fast == slow)
{
return 1;
}
}
return 0;
}
int main()
{
Node * phead = NULL;
int local = 0;
int number = 0;
scanf("%d",&number);
//链表的节点数
scanf("%d",&local);
//链表环的节点数if (number < local || local <= 0 || number <= 0)
{
printf("number MUST >= local, and MUST be positive integer\n");
exit(EXIT_FAILURE);
}phead = get_circle_link(number,local);
//link_print(phead);
int ret = 0;
if (get_circle_local(phead) == 1)
{
printf("has circle\n");
}
else
printf("no circle\n");
return 0;
}
输入：6 3
运行结果： 
文章图片
（2） 寻找环的起始点
文章图片
假设节点1到节点3距离为L，而节点3到节点5的距离为A，则有L + A = (L + A + N*X)/2，其中N为快捷点与慢节点相遇时走过的多少个环，X为1个环的环数。
因此，当判断fast=slow时，将slow和fast节点的步长都改为1步，即
slow = slow->next;
fast = fast->next;
当slow再次等于fast时，相遇的节点即为起始点
程序为:
#include
#include typedef struct node
{
int data;
struct node * next;
}Node;
Node * get_circle_link(int length, int local)
{
Node *temp = NULL;
Node *phead = NULL;
Node *tail = NULL;
int i;
//创建单链表
for (i = 0;
i < length;
i++)
{
temp = (Node *)malloc(sizeof(Node));
temp->next = NULL;
temp->data = https://www.it610.com/article/length - i;
if (phead == NULL)
{
tail = temp;
}temp->next = phead;
phead = temp;
} for (temp = phead, i =1;
i < local;
i++)
{
temp = temp->next;
}
tail->next = temp;
return phead;
}void link_print(Node *temp)
{
while (temp != NULL)
{
printf("%p:%d\t",temp,temp->data);
temp = temp->next;
getchar();
}
}//利用快慢指针判断链表是否有环
int get_circle_local(Node *phead)
{
Node * fast = phead;
Node * slow = phead;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
//fast一次跳两个节点
slow = slow->next;
//slow一次跳一个节点if (fast == slow)
{
//return 1;
for (slow = phead;
slow != fast;
)
{
slow = slow->next;
fast = fast->next;
}
return slow->data;
}
}
return 0;
}
int main()
{
Node * phead = NULL;
int local = 0;
int number = 0;
scanf("%d",&number);
//链表的节点数
scanf("%d",&local);
//链表环的节点数 if (number < local || local <= 0 || number <= 0)
{
printf("number MUST >= local, and MUST be positive integer\n");
exit(EXIT_FAILURE);
} phead = get_circle_link(number,local);
//link_print(phead);
int ret = 0;
if ((ret = get_circle_local(phead)) > 0)
{
printf("has circle,local is %d\n",ret);
}
else
printf("no circle\n");
return 0;
}
输入：6 4
结果为：
文章图片
（3）判断环的长度
当判断链表有环(slow==fast)时，设置fast的步长为2，slow的步长为1，即
slow = slow->next;
fast = fast->next->next;
当下次再次相遇时，两者的走过的距离差即为环的长度。
程序如下：
#include
#include typedef struct node
{
int data;
struct node * next;
}Node;
Node * get_circle_link(int length, int local)
{
Node *temp = NULL;
Node *phead = NULL;
Node *tail = NULL;
int i;
//创建单链表
for (i = 0;
i < length;
i++)
{
temp = (Node *)malloc(sizeof(Node));
temp->next = NULL;
temp->data = https://www.it610.com/article/length - i;
if (phead == NULL)
{
tail = temp;
}temp->next = phead;
phead = temp;
} for (temp = phead, i =1;
i < local;
i++)
{
temp = temp->next;
}
tail->next = temp;
return phead;
}void link_print(Node *temp)
{
while (temp != NULL)
{
printf("%p:%d\t",temp,temp->data);
temp = temp->next;
getchar();
}
}//利用快慢指针判断链表是否有环
int get_circle_local(Node *phead)
{
Node * fast = phead;
Node * slow = phead;
int temp = 0;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
//fast一次跳两个节点
slow = slow->next;
//slow一次跳一个节点if (fast == slow)
{while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
temp++;
if (fast == slow)
{
return temp;
}
}
}
}
return 0;
}
int main()
{
Node * phead = NULL;
int local = 0;
int number = 0;
scanf("%d",&number);
//链表的节点数
scanf("%d",&local);
//链表环的节点数 if (number < local || local <= 0 || number <= 0)
{
printf("number MUST >= local, and MUST be positive integer\n");
exit(EXIT_FAILURE);
} phead = get_circle_link(number,local);
//link_print(phead);
int ret = 0;
if ((ret = get_circle_local(phead)) > 0)
{
printf("has circle,local is %d\n",ret);
}
else
printf("no circle\n");
return 0;
}
输入：6 4
运行结果为：
文章图片
推荐阅读
