解决单链表中的环问题

 

 给定一个单链表，只给出头指针h：

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

 

问题1   如何判断是否有环

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

 

 

slow fast

 

问题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);
	}
}