4417人阅读
C/Cpp（70）
算法解析（46）
& & & &昨天去完美笔试的时候遇到以前见过的老题目，记录一下吧...
& & & &题目很简单，就是说：给你一个链表，判断是否存在环！同时求出环的入口节点！
& & & &我们先看这样一个题目：两个单链表(无环)，判断是否有公共节点！
& & & &例图：&
& & & &&* 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
struct Link *
}LINK, *p_LINK;
* 为了测试，我们将链表设计成如下：
* 1 ---& 2 ---& 3 ---& 4 ----& 5
* 6 ---& 7 ---& 8 ---& 9 ---& 2 ---& 3 ---& 4 ----& 5
void init( p_LINK * head1, p_LINK * head2 )
p_LINK tmp, save,
* 创建第一个链表
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 =
last-&next =
tmp-&next = NULL;
if ( i == 2 )
/* 保存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 =
last-&next =
tmp-&next = NULL;
last-&next =
/* 这一步是为了将链表2接上链表2后面的2节点，造成公共节点现象 */
int main()
p_LINK head1 = NULL, head2 = NULL;
p_LINK tmp1, tmp2;
init( &head1, &head2 );
* 下面这段代码用于测试你的输入是否正确( 用于自己观察 )
* while( head1 )
printf(&%d
&, head1-&value);
head1 = head1-&
* printf(&\n\n&);
while( head2 )
printf(&%d
&, head2-&value);
head2 = head2-&
* 下面开始找公共节点！
* 算法就是：先求出两个链表的长度l1和l2，再将长的那个链表的指针往后移动abs(l1-l2)，
* 再同步移动，当tmp1==tmp2就是公共节点了！
tmp1 = head1;
while( tmp1 )
tmp1 = tmp1-&
tmp2 = head2;
while( tmp2 )
tmp2 = tmp2-&
* 找公共节点
tmp1 = head1;
tmp2 = head2;
if ( l1 & l2 )
count = l1 - l2;
while( count-- )
tmp1 = tmp1-&
count = l2 - l1;
while( count-- )
tmp2 = tmp2-&
* 下面正式同步search
while( tmp1 || tmp2 )
if ( tmp1 == tmp2 )
printf(&公共节点入口值：%d\n&, tmp1-&value);
tmp1 = tmp1-&
tmp2 = tmp2-&
printf(&没有公共节点！\n&);
& & & & &&
& & & & 好，有了上面的基础，现在可以将环的问题了！
& & & & 对于一个环来说：例图：
& & & &&* 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
struct Link *
}LINK, *p_LINK;
* 为了测试，我们将链表设计成如下：
* 1 ---& 2 ---& 3 ---& 4 ----& 5
|______________|
void init( p_LINK * head )
p_LINK tmp, save,
if ( !(*head) )
(*head) = ( p_LINK )malloc( sizeof( LINK ) );
(*head)-&value = 1;
(*head)-&next = NULL;
for ( i = 2; i & 6; ++i )
tmp = ( p_LINK )malloc( sizeof( LINK ) );
tmp-&value =
last-&next =
tmp-&next = NULL;
if ( i == 3 )
/* 保存3号节点，为了最后形成环 */
if ( i == 5 )
tmp-&next =
/* 组成环状 */
int main()
p_LINK head = NULL;
p_LINK tmp1, tmp2, cut_
init( &head );
* 可以使用下面小段代码测试是否形成了环
* ( 我的意思是自己看看输出是否是你自己环的要求，并不是程序中判断环！因为程序没有眼睛 )
* while( head )
printf(&%d\n&, head-&value);
head = head-&
Sleep( 1000 );
* 下面判断链表是不是有环( 追及定理 )
* tmp1每次跑一步，tmp2每次跑两步，若有环，最终必相遇
* 若无环，tmp2是NULL结束
tmp1 = tmp2 =
cut_node = NULL;
while( tmp2 )
tmp1 = tmp1-&
/* 走一步 */
/* 注意要判断tmp2的下一个节点和下一个节点的节点是否存在！
* 不然直接tmp2 = tmp2-&next-&会导致错误！ 因为你没有判断第一个net是否存在，
* 就直接获取第一个next的next了
if ( !(tmp2-&next) )
tmp2 = tmp2-&next-&
/* 走两步 */
if ( tmp1 == tmp2 )
/* 相遇：有环 */
cut_node = tmp1;
/* 保存相遇的节点：下一步我们要从逻辑上将链表从此处切开，所以命名成cut_node */
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
* 下面计算两个链表的长度
while( tmp1 != cut_node ) /* 所谓逻辑上断开就是到了这个切点，就认为链表结束了 */
tmp1 = tmp1-&
tmp2 = cut_node-&
while( tmp2 != cut_node ) /* 所谓逻辑上断开就是到了这个切点，就认为链表结束了 */
tmp2 = tmp2-&
* 下面找到一起同步的地方
/* 初始化为两个逻辑起点 */
tmp2 = cut_
if ( l1 & l2 )
count = l1 - l2;
while( count-- )
/* 移动到相等长度处 */
tmp1 = tmp1-&
count = l2 - l1;
while( count-- )
/* 移动到相等长度处 */
tmp2 = tmp2-&
* 下面开始同步移动，找入口点
while( 1 )
if ( tmp1 == tmp2 )
printf(&入口点的值是：%d\n&, tmp1-&value);
tmp1 = tmp1-&
tmp2 = tmp2-&
/* 无环 */
printf(&链表无环！\n&);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：550549次
积分：6434
积分：6434
排名：第3706名
原创：182篇
转载：36篇
评论：82条
阅读：20637
(2)(31)(1)(5)(1)(5)(3)(1)(10)(2)(3)(1)(1)(2)(3)(1)(36)(2)(3)(4)(101)推荐这篇日记的豆列
&&&&&&&&&&&&算法（49）
& 由编程之美P261页下面程序改错涉及开来。
判断有没有环比较容易，设两个指针指向头节点，一个快点走，一个慢点走，如果有环，两者必会相遇。这里我们设一个一次走两步，一个一次走一步
&& 关键是要找到环的入口地址：
下面证明如何得到入口地址
假设环长为L，起始点到环入口长度为a，环长度为r，设慢指针和快指针相遇前，慢指针在环内走了x步（快指针已经走了n圈），同时假设慢指针已经走了s步，则快指针走了2s步。
则有：2S = S + n r & ；则s =
又 a + X &= S；故a+X = nr = (n-1)r+r = (n-1)r + L-a；则a = (n-1)r + L-a-X；含义为环入口距离起点的距离和相遇点距离环入口点的距离相等。
这里a = (n-1)r + L-a-X
可能比较难理解，可以这样想，假设两个指针，一个从头节点开始走，一个从相遇点开始走，两个都一步步走
当走了a（长度）之后，头节点开始走的现在刚好走到了环的入口地址（这个可以理解吧）
从相遇点走的也走了a步我们由上面知道a = (n-1)r + L-a-X&&&&&& (n-1)r 为环得到长度倍数，可以看成先走的，那么此时走了（n-1）r又回到了相遇点，接着走剩下的 L-a-x，L-a为环长，L-a-x为环中剩下的距离，所有相遇点走的也刚好走到了环口。
故让慢指针回到起点，快指针从相遇点开始继续走，当两者相等时，则为环入口地址。
代码如下：
node* first_loop_port(node *head)
node *slow = head, *fast =
while ( fast && fast-&next )
slow = slow-&
fast = fast-&next-&
if ( slow == fast )
if (fast == NULL || fast-&next == NULL)
return NULL;
while (slow != fast)
slow = slow-&
fast = fast-&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：181320次
积分：3041
积分：3041
排名：第11373名
原创：121篇
评论：28条
(9)(4)(7)(5)(3)(4)(4)(19)(27)(15)(8)(4)(2)(2)(3)(6)(5)
文章：11篇
阅读：17007判断一个单链表是否有环及环的链接点(转)
给定一个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度
void Isloop(Llink head)
&if(!head||!head-&next)
&Llink p,q;
&bool loop=
&p=q=head-&
&while(q&&q-&next)//判断是否有环
&&q=q-&next-&
&&if(p==q)
&if(!loop)
&&cout&&"This
link has not loop\n";
&&cout&&"This
link has a loop\n";
&&Llink r=p;
&&q=head-&
nonloop=1,loopcount=1;
//nonloop计算非环结点数，loopcount计算环上结点数
&&do//计算环上的结点数
&&}while(p!=r);
&&while(p!=q)//得到环的入口结点，同时计算得到非环的结点数
&&cout&&"\nStart
"&&p-&data&&&&
&&cout&&"\nCount
of nonloop: "&&nonloop
&&"\nCount of loop:
"&&loopcount
&&"\nCount of Linknode:
"&&nonloop+loopcount&&
判断是否存在环的程序：
bool&IsExitsLoop(slist&*head)&&
&&&&slist&*slow&=&head,&*fast&=&&&
&&&&while&(&fast&&&&fast-&next&)&&&
&&&&&&&&slow&=&slow-&&&
&&&&&&&&fast&=&fast-&next-&&&
&&&&&&&&if&(&slow&==&fast&)&break;&&
&&&&return&!(fast&==&NULL&||&fast-&next&==&NULL);&&
寻找环连接点（入口点）的程序：
slist*&FindLoopPort(slist&*head)&&
&&&&slist&*slow&=&head,&*fast&=&&&&&
&&&&while&(&fast&&&&fast-&next&)&&&
&&&&&&&&slow&=&slow-&&&
&&&&&&&&fast&=&fast-&next-&&&
&&&&&&&&if&(&slow&==&fast&)&break;&&
&&&&if&(fast&==&NULL&||&fast-&next&==&NULL)&&
&&&&&&&&return&NULL;&&
&&&&slow&=&&&
&&&&while&(slow&!=&fast)&&
&&&&&&&&&slow&=&slow-&&&
&&&&&&&&&fast&=&fast-&&&
&&&&return&&&
亦可以用类似与hash表的方法，即设立一个数组，将链表结点中的值做数组下标，当赋值冲突时就是环的接入点
isloop(Llink p)
&if(!p||!p-&next)
&int a[MAXSIZE],n=0;
&memset(a,0,sizeof(int)*MAXSIZE);
&&if(a[p-&data]==-1)//存在环时，会发生冲突
&&&cout&&"\nLoop
"&&p-&data&&endl
&&&&&&"\nLen
&&a[p-&data]=-1;
Llink CreatlinkLoop()
//创建一个有环的链表
&Llink head=new L
&//head-&data=0;
&head-&next=NULL;
&cout&&"input
&while(cin&&e)
&&Llink p=new L
&&p-&data=e;
&&p-&next=q-&
&&q-&next=p;
&cin.clear();
&cin.sync();
&srand(time(0));
&q-&next=Findnode(head,rand()%N);//随机产生环的接入点
Llink Findnode(Llink head,int n)//找出链表中的第n个结点
&Llink p=head-&
i=1;p&&i&n;++i)
////////////////////////////////////////////////////////
问题2的证明如下：
链表形状类似数字 6 。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。
分析追赶过程:
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x&=a 。
连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。
根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而
S(x+a) 必然在环上。所以可以发生碰撞。
而，同为前进 a 步，同为连接点，所以必然发生碰撞。
综上，从 x
点和从起点同步前进，第一个碰撞点就是连接点。
/////////////////////////////////////////////////////////////
假设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为x，环的长度为r，慢指针总共走了s步，则快指针走了2s步。另外，快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离)，得到以下关系：
2s = a + nr +
=&a = nr -
由上式可知：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点，搞掂！
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。}