判断链表是否有环 、 找到环的入口节点
昨天去完笔试的时候遇到以前见过的老题目，记录一下吧...
题目很简单，就是说：给你一个链表，判断是否存在环！同时求出环的入口节点！
我们先看这样一个题目：两个单链表(无环)，判断是否有公共节点！
例图：
* 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>#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;}