判断链表是否有环、找到环的入口节点

迈不过友情╰ 2022-09-17 12:23 151阅读 0赞

昨天去完美笔试的时候遇到以前见过的老题目，记录一下吧...

题目很简单，就是说：给你一个链表，判断是否存在环！同时求出环的入口节点！

我们先看这样一个题目：两个单链表(无环)，判断是否有公共节点！

例图：

\* 1 ---> 2 ---> 3 ---> 4 ----> 5  
        \*                
        \* 6 ---> 7 ---> 8 ---> 9 ---> 2 ---> 3 ---> 4 ----> 5

我们认为上面两个链表是存在公共点，从值为2的点开始！(  为了简单起见，每个node的值不一样 )

那么基本的算法就是：因为若有公共的点，那么公共点之后的链表肯定是一样的，也就是长度一样！

那么我们先对两个链表求长度l1和l2，将较长的链表先往后移动指针abs(l1-l2)位，然后再同步移动，每次

判断一下是否是一样的node，直到找到第一个公共点！

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Link
    {
    	int value;
    	struct Link * next;
    }LINK, *p_LINK;
    
    /**
     * 为了测试，我们将链表设计成如下：
     * 1 ---> 2 ---> 3 ---> 4 ----> 5
     *              
     * 6 ---> 7 ---> 8 ---> 9 ---> 2 ---> 3 ---> 4 ----> 5           
     *
     */
    void init( p_LINK * head1, p_LINK * head2 )
    {
    	int i;
    	p_LINK tmp, save, last;
    	
    	/**
    	 * 创建第一个链表
    	 */
    	if ( !(*head1) )
    	{
    		(*head1) = ( p_LINK )malloc( sizeof( LINK ) );
    		(*head1)->value = 1;
    		(*head1)->next = NULL;
    		last = *head1;
    	}
    
    	for ( i = 2; i < 6; ++i )
    	{
    		tmp = ( p_LINK )malloc( sizeof( LINK ) );
    		tmp->value = i;
    		last->next = tmp;
    		tmp->next = NULL;
    		last = tmp;
    
    		if ( i == 2 )
    		{
    			save = tmp;				/* 保存2号节点，为了第二个链表接上此节点 */		
    		}
    	}
    
    	/**
    	 * 创建第二个链表
    	 */
    	if ( !(*head2) )
    	{
    		(*head2) = ( p_LINK )malloc( sizeof( LINK ) );
    		(*head2)->value = 6;
    		(*head2)->next = NULL;
    		last = *head2;
    	}
    
    	for ( i = 7; i < 10; ++i )
    	{
    		tmp = ( p_LINK )malloc( sizeof( LINK ) );
    		tmp->value = i;
    		last->next = tmp;
    		tmp->next = NULL;
    		last = tmp;
    	}
    
    	last->next = save;				/* 这一步是为了将链表2接上链表2后面的2节点，造成公共节点现象 */
    }
    
    int main()
    {
    	p_LINK head1 = NULL, head2 = NULL;
    	p_LINK tmp1, tmp2;
    	int    l1, l2, count;
    
    	init( &head1, &head2 );
    
    	/** 
    	 * 下面这段代码用于测试你的输入是否正确( 用于自己观察 )
    	 *
    	 *	while( head1 )
    	 *	{
    	 *		printf("%d  ", head1->value);
    	 *		head1 = head1->next;
    	 *	}
    	 *	printf("\n\n");
    	 *	 while( head2 )
    	 *	{
    	 * 		printf("%d  ", head2->value);
             *		head2 = head2->next;
    	 *	}
    	 */
    
    	/**
    	 * 下面开始找公共节点！
    	 * 算法就是：先求出两个链表的长度l1和l2，再将长的那个链表的指针往后移动abs(l1-l2)，
    	 * 再同步移动，当tmp1==tmp2就是公共节点了！
    	 */
    	
    	/**
    	 * 求长度
    	 */
    	tmp1 = head1;
    	l1 = 0;
    	while( tmp1 )
    	{
    		++l1;
    		tmp1 = tmp1->next;
    	}
    
    	tmp2 = head2;
    	l2 = 0;
    	while( tmp2 )
    	{
    		++l2;
    		tmp2 = tmp2->next;
    	}
    
    	/**
    	 * 找公共节点
    	 */
    	tmp1 = head1;
    	tmp2 = head2;
    
    	if ( l1 > l2 )
    	{
    		count = l1 - l2;
    		while( count-- )
    		{
    			tmp1 = tmp1->next;
    		}
    	}
    	else
    	{
    		count = l2 - l1;
    		while( count-- )
    		{
    			tmp2 = tmp2->next;
    		}
    	}
    	
    
    	/**
    	 * 下面正式同步search
    	 */
    	while( tmp1 || tmp2 )
    	{
    		if ( tmp1 == tmp2 )
    		{
    			printf("公共节点入口值：%d\n", tmp1->value);
    			return 0;
    		}
    		tmp1 = tmp1->next;
    		tmp2 = tmp2->next;
    	}
    
    	printf("没有公共节点！\n");
    
    	return 0;
    }

好，有了上面的基础，现在可以将环的问题了！

对于一个环来说：例图：

\* 1 ---> 2 ---> 3 ---> ... ---> 4 ----> 5  
        \*                     ^                              |  
        \*                     |\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_|

我们可以使用“ 追及定理 ”判断是否有环！给两个指针初始化都指向头，一个一次走一步，另一个走两步，最后

若相遇则有环，否则无环会遇到NULL退出。

基于这个思想，我们只能判断是否有环！那么之后呢？怎么找到那个入口节点！因为我们知道，若相遇，那么入

口节点肯定在这个环里面，那么我们在**逻辑上**将链表分开(剪开)，如图：

\* 1 ---> 2 ---> 3 ... ---> 4

\* 5 ---> 3 ... ---> 4

那么现在成了一个什么问题？求第一个公共节点的问题！就是上面的已经说过的那个问题了！

#include <stdio.h>
    #include <stdlib.h>
    #include <windows.h>
    
    typedef struct Link
    {
    	int value;
    	struct Link * next;
    }LINK, *p_LINK;
    
    /**
     * 为了测试，我们将链表设计成如下：
     * 1 ---> 2 ---> 3 ---> 4 ----> 5
     *               ^              |
     *               |______________| 
     *
     */
    void init( p_LINK * head )
    {
    	int i;
    	p_LINK tmp, save, last;
    	
    	if ( !(*head) )
    	{
    		(*head) = ( p_LINK )malloc( sizeof( LINK ) );
    		(*head)->value = 1;
    		(*head)->next = NULL;
    		last = *head;
    	}
    
    	for ( i = 2; i < 6; ++i )
    	{
    		tmp = ( p_LINK )malloc( sizeof( LINK ) );
    		tmp->value = i;
    		last->next = tmp;
    		tmp->next = NULL;
    		last = tmp;
    
    		if ( i == 3 )
    		{
    			save = tmp;			/* 保存3号节点，为了最后形成环 */		
    		}
    
    		if ( i == 5 )
    		{
    			tmp->next = save;		/* 组成环状 */
    		}
    	}
    }
    
    int main()
    {
    	p_LINK head = NULL;
    	p_LINK tmp1, tmp2, cut_node;
    	int    l1, l2, count;
    	
    	init( &head );
    
    	/**
    	 * 可以使用下面小段代码测试是否形成了环
    	 * ( 我的意思是自己看看输出是否是你自己环的要求，并不是程序中判断环！因为程序没有眼睛 )
    	 * 
    	 * while( head )
    	 * {
    	 *		printf("%d\n", head->value);
         	 *		head = head->next;
    	 *		Sleep( 1000 );
    	 * }
    	 */
    
    	/**
    	 * 下面判断链表是不是有环( 追及定理 )
    	 * tmp1每次跑一步，tmp2每次跑两步，若有环，最终必相遇
    	 * 若无环，tmp2是NULL结束
    	 * 
    	 */
    	tmp1 = tmp2 = head;
    	cut_node = NULL;
    
    	while( tmp2 )
    	{
    		tmp1 = tmp1->next;			/* 走一步 */
    
    		/* 注意要判断tmp2的下一个节点和下一个节点的节点是否存在！
    		 * 不然直接tmp2 = tmp2->next->next;会导致错误！ 因为你没有判断第一个net是否存在，
    		 * 就直接获取第一个next的next了
    		 */
    		if ( !(tmp2->next) )
    		{
    			break;
    		}
    			
    		tmp2 = tmp2->next->next;		/* 走两步 */
    
    		if ( tmp1 == tmp2 )			/* 相遇：有环 */
    		{
    			cut_node = tmp1;		/* 保存相遇的节点：下一步我们要从逻辑上将链表从此处切开，所以命名成cut_node */
    			break;
    		}
    	}
    
    	if ( cut_node )					/* 存在环 */
    	{
    		printf("链表存在环！\n");
    
    		/**
             	 * 下面就要找环入口节点了！
    		 * 我们的思想借助于上面的：求两个链表是否有公共节点！
    		 * 1 ---> 2 ---> 3 ---> 4 ----> 5
    		 *               ^              |
    		 *               |______________| 
    		 * 对于上面的链表，比如从5处相遇，那么cut_node=4的那个node，从4处逻辑上断开变成：
    		 *
    		 * 1 ---> 2 ---> 3 ---> 4
    		 *        5 ---> 3 ---> 4
    		 * 就变成了找公共节点的问题了！
    		 * 
    		 * 那么一般的算法是：求出链表1的长度l1，链表2的长度l2，然后，移动指针，使得后面的长度相等，
    		 * 再同步移动！遇到第一个相遇的点就是入口节点！Yes
    		 *
    		 * 对于上面的链表就是分别从2和5开始移动，到3的时候就是OK的了！
    		 * 
    		 * 但是上面的图示在本例子是不对的，本例子是在4处断开的，所以图示是：
    		 * 
    		 * 1 ---> 2 ---> 3
    		 * 4 ---> 5 ---> 3  
    		 */
    
    		/**
    		 * 下面计算两个链表的长度
    		 */
    		l1 = 0;
    		tmp1 = head;
    		while( tmp1 != cut_node )	/* 所谓逻辑上断开就是到了这个切点，就认为链表结束了 */
    		{
    			++l1;
    			tmp1 = tmp1->next;
    		}
    		
    		tmp2 = cut_node->next;
    		l2 = 1;
    		while( tmp2 != cut_node )	/* 所谓逻辑上断开就是到了这个切点，就认为链表结束了 */
    		{
    			++l2;
    			tmp2 = tmp2->next;
    		}
    
    		/**
    		 * 下面找到一起同步的地方
    		 */
    
    		tmp1 = head;				/* 初始化为两个逻辑起点 */
    		tmp2 = cut_node;
    
    		if ( l1 > l2 )
    		{
    			count = l1 - l2;
    			while( count-- )		/* 移动到相等长度处 */
    			{
    				tmp1 = tmp1->next;
    			}
    		}
    		else
    		{
    			count = l2 - l1;
    			while( count-- )		/* 移动到相等长度处 */
    			{
    				tmp2 = tmp2->next;
    			}
    		}
    
    		
    		/**
    		 * 下面开始同步移动，找入口点
    		 */
    		while( 1 )
    		{
    			if ( tmp1 == tmp2 )
    			{
    				printf("入口点的值是：%d\n", tmp1->value);
    				break;
    			}
    
    			tmp1 = tmp1->next;
    			tmp2 = tmp2->next;
    		}
    
    	}
    	else							/* 无环 */
    	{
    		printf("链表无环！\n");
    	}
    
    	return 0;
    }