环形链表有关题目解析

环形链表相关题目解析

环形链表也是近年来面试笔试中常考问题，于是就在网上整理了相关的题目与解析。

1.判断一个链表是不是环形链表

思路：这里给定两个指针，fast和slow。两个指针同时从头结点开始出发，fast指针走两步，slow指针走一步；若链表有环，这两个指针肯定会在某点相遇；若链表无环，fast会直接先到达NULL。

代码：

bool Iscircle(Node *head)//判断是否有环
{
   Node *slow=head;
   Node *fast=head;

   if(head==NULL||head->next==NULL)
	return false;


   while(slow!=NULL&&fast!=NULL&&fast->next!=NULL)
   {
	   fast=fast->next->next;
	   slow=slow->next;

	   if(fast==slow)
		   return true;
   }
   return false;
}

2.环形链表的起始位置

思路：按照上面的思路，假设两个指针在（图Z点）相遇，此时slow指针走过的路径是a+b，而fast指针走过的路径是a+b+c+b。由于fast的步长是slow的两倍，因此可以得到：2（a+b）=a+b+c+b，解得a=c。由上图可以看出从X点到Y点的距离与从Z点到Y点的距离相等，即让slow指针与fast指针相遇后，我们让slow指针再指向头结点（X点），此时fast指针位置不变，再让slow和fast指针同时后移，当两个指针相遇时，slow和fast指向的是恰好是环形链表的起始节点（Y点）。

代码：

Node* BeginNode(Node *head)
{
	Node *slow = head;
	Node *fast = head;

	if(head==NULL||head->next==NULL)
		return NULL;

	while(slow!=NULL&&fast!=NULL&fast->next!=NULL)//找到相遇点
	{
		slow=slow->next;
		fast=fast->next->next;

		if(slow==fast)
			break;
	}

	if(fast==NULL)
		return NULL;

	slow=head;//从头开始

	while(slow!=fast)
	{
		slow=slow->next;
		fast=fast->next;
	}
	
	return fast;
}

3.求解环的长度

思路：如上图所示：环的长度为b+c ，由上题可知 a=c，环的长度即为a+b，即slow指针所走过的步长。

4.判断两个链表是不是相交的

思路：若果两个链表相交，那么这两个链表的尾节点一定相同。直接判断尾节点是否相同即可。这里把这道题放在环形链表，因为环形链表可以拆成Y字的两个链表。