解决单链表中的环问题

时间:2022-12-13 14:01:54

 

 给定一个单链表,只给出头指针h:

  1. 如何判断是否存在环?
  2. 如何知道环的长度?
  3. 如何找出环的连接点在哪里?
  4. 带环链表的长度是多少?

 

问题1   如何判断是否有环

使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。

 

问题2   如何判断环的长度

相遇点出同时出发,fast指针和slow指针再次相遇时,slow指针走过的点的个数就是环的长度。试问会不会slow在不到一圈的地方两者相遇呢?不会,因为假设slow走s,则fast走2s。二者相遇则二者距离必相差圈数的倍数,即:2s-s = k*圈距离=s。此时k=1。因此得出结论:从相遇到再次相遇,slow再走完整的一圈。

 

问题3   如何找出环的连接点

定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。                                           

证明:

链表形状类似数字6。 
假设甩尾(在环外)长度为 a(结点个数),环内长度为 b 。 
则总长度(也是总结点数)为 a+b 。 
从头开始,0 base 编号。 
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i<a 时,S(i)=i ; 
当 i≥a 时,S(i)=a+(i-a)%b 。

分析追赶过程。 
两个指针分别前进,假定经过 x 步后,碰撞。则有:S(x)=S(2x)
由环的周期性有:2x=tb+x 。得到 x=tb 。 
另,碰撞时,必须在环内,不可能在甩尾段,有 x>=a 。

连接点为从起点走 a 步,即 S(a)。 
S(a) = S(tb+a) = S(x+a)。 
得到结论:从碰撞点 x 前进 a 步即为连接点

根据假设易知 S(a-1) 在甩尾段,S(a) 在环上,而 S(x+a) 必然在环上。所以可以发生碰撞。 又,同为前进 a 步,同为连接点,所以必然发生碰撞。

综上,从 x 点和从起点同步前进,第一个碰撞点就是连接点。

 

问题4   带环链表的长度是多少

问题2知道环的长度,问题3知道环外边的长度。两者相加即为总长度。

 

参考代码

#include <stdlib.h>
#include <stdio.h>

typedef struct node
{
int data;
struct node *next;
}node;

node *Create_list() //建立链表
{
node *p_return, *p;
p_return = NULL;

node *n1 = (node *)malloc(sizeof(node));
n1->data = 1;
n1->next = NULL;
p = n1;
p_return = p;

node *n2 = (node *)malloc(sizeof(node));
n2->data = 2;
n2->next = NULL;
p->next = n2;
p = n2;

node *n3 = (node *)malloc(sizeof(node));
n3->data = 3;
n3->next = NULL;
p->next = n3;
p = n3;

node *n4 = (node *)malloc(sizeof(node));
n4->data = 4;
n4->next = NULL;
p->next = n4;
p = n4;

node *n5 = (node *)malloc(sizeof(node));
n5->data = 5;
n5->next = NULL;
p->next = n5;
p = n5;

node *n6 = (node *)malloc(sizeof(node));
n6->data = 6;
n6->next = NULL;
p->next = n6;
p = n6;

p->next = n3;

return p_return;
}

node *find_in_node(node *p1, node *p2) //找到入环的结点
{
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
int get_out_len(node *p1, node *p2) //计算出环外边的长度
{
int num = 0;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
num++;
}
return num;
}

node *check_loop(node *p) //检查是否有环
{
node *p_slow, *p_fast;
p_slow = p;
p_fast = p;
int tag = 0;
while(p_slow && p_fast->next)
{
p_slow = p_slow->next;
p_fast = p_fast->next->next;
if(p_slow == p_fast)
{
tag = 1;
break;
}
}
if(tag == 1)
{
printf("Have loop\n");
return p_slow;
}
else
{
printf("Not have loop\n");
return NULL;
}
}
int get_len_loop(node *var_loop) //得出环的长度
{
node *p = var_loop->next;
int num = 1;
while(p != var_loop)
{
p = p->next;
num++;
}
return num;
}

int main()
{
node *p = Create_list();
node *coin_loop = check_loop(p);
if(coin_loop)
{
int len_loop = get_len_loop(coin_loop);
printf("Length of Loop is:%d\n", len_loop);
node *in_node = find_in_node(p, coin_loop);
int len_out = get_out_len(p, coin_loop);
printf("Length of out Loop is %d\n", len_out);
printf("Length of all is %d\n", len_out + len_loop);
}
}