快慢指针求单链表环

2013年8月30日 由 Creater 留言 »

问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个环,在顺序遍历链表的时候,程序就会陷入死循环。如下即为一个带环的单链表。link_circle
      如何检测一个链表中是否有环,如果检测到环,如何确定环的入口点(即求出环长,环前面的链长)。
      想象一下在跑道上跑步:两个速度不同的人在操场跑道上一圈一圈地跑,他们总会有相遇的时候。因此我们只需要准备两个指针,同时从链表头出发,一个每次往前走一步,另一个每次往前走两步。如果链表没有环,那么经过一段时间,第二个(速度较快的)指针就会到达终点;但如果链表中有环,两个指针就会在环里转圈,并会在某个时刻相遇。
     大家也许会问,这两个指针要在环里转多少圈才能相遇呢?会不会转几千几万圈都无法相遇?
     实际上,第一个(速度慢的)指针在环里转满一圈之前,两个指针必然相遇。不妨设环长为L,第一个指针P1第一次进入环时,第二个指针P2在P1前方第a个结点处(0 < a < L),设经过x次移动后两个指针相遇,那么应该有x = a + 2x (mod L)[因为P1刚进入环,P2已经在环中移动了a步,那么P1在环里移动x步(P1还没有完成一圈)后,P2则应该在环里共移动了2*x+a步,这个2*x+a可能是p2已经遍历该环很多次],由x = a + 2x (mod L)
      当P2未完成一圈时,x = -a;
      当P2已经超出一圈时,x = L-a;
      显然x = L-a即可满足。
     下面这张图可以清晰地表明这种关系,经过x = L-a次移动,P1向前移动了L-a个位置(相当于后退了a),到达P1′处,而P2向前移动了2L-2a个位置(相当于后退了2a),到达P2′处,显然P1′和P2′是同一点。故在P1还未走满一周时,两快慢指针即可相遇。

two_pointers_in_ring

       在知道链表内有环后,求环长是一件非常简单的事情,只要从刚才那个相遇点开始,固定P2,继续移动P1,直到P1与P2再次相遇,所经过的步数就是环长。

       怎么求环前面那段子链的长度呢?很简单,有两种方法:

       1.让P1和P2都回到链表起点,然后让P2先往前走L次(每次往前走一步),然后P1和P2再同时往前走,当它们再次相遇时,P1所走的步数就是环前面的子链长度。道理很简单:设链的总长度为m,那么前边的子链长度为m-l,所以让指针P2先走L次,则剩下m-l次就可以到达环的相遇点,而P1距离环的相遇点距离也为m-l.

      2.让P2固定在相遇点,P1回到链表头,两指针同时移动直到相遇时即为环的入口,而且P1移动的次数即为子链长度。道理也很简单,由上边的图可以知道,快慢指针相遇时,慢指针在环里移动了L-a步(或者认为后退了a步),也即是再移动a步就可以到达环的入口。另外如图当P1最开始进入环时,P2已经在环内移动了a步,我们知道p2移动的距离是P1移动距离的两倍,所以子链的长度即为a。

广告位

发表评论

你必须 登陆 方可发表评论.