8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？

深碍√TFBOYSˉ_ 2022-05-26 10:08 165阅读 0赞

判断单链表是否有环？

思路：

快慢指针，快指针每次走两步，慢指针每次走一步。

每次判断快指针是否到头了以及快慢指针是否指向同一元素。

快指针走到头了，则没有环；

如果快指针和慢指针指向同一个元素，则有环。

如何找到环的起始点？

思路：

如果有环，则快慢指针一定相遇在环上。

将环从快慢指针相遇结点剪开，则变成了两个单链表相交的问题。

设两个单链表的长度分别为N，M，用两个指针分别指向两链表第一个结点，

让位于长链表上的指针先走abs（N-M）步。然后一起走，相遇时则为环的起始点。

如何知道环的长度？

绕一圈即可。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //建立链表
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    //输出链表
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    //找到第index个元素
    struct node * find_node(struct node* phead, int index )
    {
    	if(!phead) return NULL;
    	struct node * pNode = phead;
    	while( index--)
    	{
    		pNode = pNode->next;
    		if( !pNode )
    			return NULL;
    	}
    	return pNode;
    }
    
    
    
    //检查链表有无环
    //有，则返回快慢指针共同指向的点
    //无，则返回空指针
    struct node * check_loop( struct node * phead )
    {
    	if(!phead)
    		 return NULL;
    	struct node * pFast = phead;
    	struct node * pSlow = phead;
    
    	int step = 1;
    	while( pFast )
    	{
    		pFast = pFast->next;
    		if( step++%2==0 )
    		{
    			pSlow = pSlow->next;
    			if( pSlow == pFast )
    				return pSlow;
    		}
    	}
    	return NULL;
    }
    
    //求两个节点的距离，即中间有多少个连线
    //返回-1为出错，如果是同一节点，则返回0
    int find_length( struct node* pNode1, struct node* pNode2 )
    {
    	if(!pNode1||!pNode2) return -1;
    
    	int len=0;
    	while( pNode1 )
    	{
    		if( pNode1 == pNode2 )
    			return len;
    		pNode1 = pNode1->next;
    		len++;
    	}
    	return -1;
    }
    
    //找环的起始点,pTail为快慢指针共同指向的节点
    struct node * loop_first_node( struct node * phead, struct node * pTail )
    {
    	if( !phead || !pTail ) return NULL;
    	struct node * pNode1 = pTail->next;
    	struct node * pNode2 = phead->next;
    	int M = find_length( pNode1, pTail );
    	int N = find_length( pNode2, pTail );
    
    	if( M > N )
    	{
    		int step = M-N;
    		while(step--)
    			pNode1 = pNode1->next;
    	}
    	if( N > M )
    	{
    		int step = N-M;
    		while(step--)
    			pNode2 = pNode2->next;
    	}
    	while(pNode1&&pNode2)
    	{
    		if(pNode1 == pNode2 )
    			return pNode1;
    		pNode1 = pNode1->next;
    		pNode2 = pNode2->next;
    	}
    	return NULL;
    }
    
    void test()
    {
    	string str;
    	cin >> str;
    	struct node *phead = create( str );
    	
    	int index;
    	cin >> index;
    	struct node * pNode1 = find_node( phead, index );
    	struct node * pNode = phead;
    	while( pNode->next )
    		pNode = pNode->next;
    	pNode->next = pNode1;        //生成有环链表, 注释掉之一行则为无环链表
    	struct node * pTail = check_loop( phead );
    	struct node * pFirstLoopNode = NULL;
    	if( pTail )
    	{	
    		cout <<"The link has loop." <<endl;
    		pFirstLoopNode = loop_first_node(phead, pTail);
    		cout <<"First Loop Node is: " << pFirstLoopNode->val <<endl;
    		cout <<"The number of node in loop is: " << find_length( pTail->next, pTail)+1 <<endl;
    	}
    	else
    		cout << "The link table has no loop." <<endl;
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	return 0;
    }