链表面试题之带环问题

超、凢脫俗 2022-09-21 13:03 197阅读 0赞

# 面试题一：判断链表是否带环，如果链表带环则返回相遇点 #

pLinkNode Check\_Cycle(pLinkList plist);

首先先给出代码的结构实现：

typedef int DataType;
    
    typedef struct LinkNode
    {
    	DataType data;
    	struct LinkNode *next;
    }LinkNode,*pLinkNode;    
    
    typedef struct LinkList
    {
    	LinkNode *phead;
    }LinkList,*pLinkList;

看到这道问题如何去分析呢？我们可以类比运动员在操场上赛跑的实例，如果一个运动员跑的快另一个跑的慢，那仫这两个运动员必然会在操场相遇；假设我们链表中的环就是操场，存在两个指针，一个快指针，一个慢指针，如果链表带环那仫这两个指针必定会在操场上的某一点相遇，这就判断了链表是否带环的问题啦！在这里就用到了我们之前提到的快慢指针的问题了，代码实现如下：

pLinkNode Check_Cycle(pLinkList plist)   //判断链表是否带环,若带环则返回相遇点
    {
    	pLinkNode fast=NULL;
    	pLinkNode slow=NULL;
    	assert(plist);
    	fast=plist->phead;
    	slow=plist->phead;
    	while(fast && fast->next)
    	{
    		fast=fast->next->next;
    		slow=slow->next;
    		if(fast == slow)
    		{
    			return fast;
    		}
    	}
    	return NULL;
    }

#  面试题二.若链表带环则求出环的长度和环的入口点 #

int Get\_CircleLength(pLinkNode meet); //求带环链表环的长度

pLinkNode GetCircle\_EntryNode(pLinkList plist,pLinkNode meet); //求带环链表环的入口点

如何求带环链表的长度呢？在上述判断链表是否带环的实现中我们找到了两个指针的相遇点，当然如果我们从相遇点遍历链表，每遍历一次count就自加一次当再次遍历到相遇点时也就统计出了带环链表的长度；代码实现如下

int Get_CircleLength(pLinkNode meet)     //求环的长度
    {
    	int count=1;
    	pLinkNode cur=meet;
    	pLinkNode pmeet=meet;
    	while(cur->next != pmeet)
    	{
    		count++;
    		cur=cur->next;
    	}
    	return count;
    }

如何求带环链表的入口点呢？请看下列推导过程：

![Center][]

由上述推导的等式x=n\*L-y, 可以知道要求出环的入口点必须设置两个指针，一个指针指向链表的第一个结点，一个指针指向环内的相遇点，同时开始遍历链表，那仫经历过n圈遍历后两个指针必然指向同一个结点，这个结点就是环的入口点，详细分析可见上图，代码实现如下：

pLinkNode GetCircle_EntryNode(pLinkList plist,pLinkNode meet)   //获取环的入口点
    {
    	pLinkNode front=plist->phead;
    	pLinkNode back=meet;
    	assert(plist);
    	while(front != back)
    	{
    		front=front->next;
    		back=back->next;
    	}
    	return front;
    }

测试结果如下：

![Center 1][]

void text7()
    {
    	int ptr=0;
    	pLinkNode ret=NULL;
    	pLinkNode meet=NULL;
    	LinkList plist;
    	Init_LinkList(&plist);
    	Push_back(&plist,1);
    	Push_back(&plist,2);
    	Push_back(&plist,3);
    	Push_back(&plist,4);
    	Push_back(&plist,5);
    	ret=Find_NUM(&plist,5);  //构造环
    	ret->next=Find_NUM(&plist,3);
    
    	meet=Check_Cycle(&plist);
    	if(meet != NULL)
    	{
    		printf("带环链表的相遇结点为:%d\n",meet->data);
    		ptr=Get_CircleLength(meet);
    		printf("带环链表的环的长度为:%d\n",ptr);
    		ret=GetCircle_EntryNode(&plist,meet);
    		printf("带环链表的环的入口点为:%d\n",ret->data);
    	}
    	Free_LinkList(&plist);
    }
    
    int main()
    {
    	text7();
    	system("pause");
    	return 0;
    }

本文如有缺陷请读者指出，共同进步！！！

[Center]: /images/20220721/a00204a0b0334bd2b736ad7f6d6a6155.png
[Center 1]: /images/20220721/53a6402a3a834cb7bad9c879786e483d.png