Given a linked list, determine if it has a cycle in it.

Have you met this question in a real interview??YesExample

Given -21->10->4->5, tail connects to node index 1, return true

Challenge?

Follow up:
Can you solve it without using extra space?

來(lái)源：?http://www.lintcode.com/en/problem/linked-list-cycle/

分析

---

使用快慢指針

1234567891011121314151617181920212223242526272829

/**?*?Definition?for?ListNode.?*?public?class?ListNode?{?*?????int?val;?*?????ListNode?next;?*?????ListNode(int?val)?{?*?????????this.val?=?val;?*?????????this.next?=?null;?*?????}?*?}?*/?public?class?Solution?{????/**?????*?@param?head:?The?first?node?of?linked?list.?????*?@return:?True?if?it?has?a?cycle,?or?false?????*/????public?boolean?hasCycle(ListNode?head)?{??????????//?write?your?code?here????????ListNode?slow?=?head,?fast?=?head;????????while(fast?!=?null?&&?fast.next?!=?null?&&?fast.next.next?!=?null){????????????slow?=?slow.next;????????????fast?=?fast.next.next;????????????if(slow?==?fast){????????????????return?true;????????????}????????}????????return?false;????}}

1.判斷單鏈表是否有環(huán)

　　使用兩個(gè)slow, fast指針從頭開(kāi)始掃描鏈表。指針slow 每次走1步，指針fast每次走2步。如果存在環(huán)，則指針slow、fast會(huì)相遇；如果不存在環(huán)，指針fast遇到NULL退出。

　　就是所謂的追擊相遇問(wèn)題： 相遇時(shí)，slow 并沒(méi)有走完一圈，fast領(lǐng)先slow一圈，第一次相遇在Pos處

　　　　

2.求有環(huán)單鏈表的環(huán)長(zhǎng)

?　　在環(huán)上相遇后，記錄第一次相遇點(diǎn)為Pos，之后指針slow繼續(xù)每次走1步，fast每次走2步。在下次相遇的時(shí)候fast比slow正好又多走了一圈，也就是多走的距離等于環(huán)長(zhǎng)。

　　設(shè)從第一次相遇到第二次相遇，設(shè)slow走了len步，則fast走了2*len步，相遇時(shí)多走了一圈：?

　　　　環(huán)長(zhǎng)=2*len-len。?

3.求有環(huán)單鏈表的環(huán)連接點(diǎn)位置

　　第一次碰撞點(diǎn)Pos到連接點(diǎn)Join的距離 = 頭指針到連接點(diǎn)Join的距離，因此，分別從第一次碰撞點(diǎn)Pos、頭指針head開(kāi)始走，相遇的那個(gè)點(diǎn)就是連接點(diǎn)。

?　　　　

　　在環(huán)上相遇后，記錄第一次相遇點(diǎn)為Pos，連接點(diǎn)為Join，假設(shè)頭結(jié)點(diǎn)到連接點(diǎn)的長(zhǎng)度為LenA，連接點(diǎn)到第一次相遇點(diǎn)的長(zhǎng)度為x，環(huán)長(zhǎng)為R。

　　　　第一次相遇時(shí)，slow走的長(zhǎng)度 S =?LenA?+?x;

　　　　第一次相遇時(shí)，fast走的長(zhǎng)度 2S =?LenA?+ n*R?+?x;

　　　　所以可以知道，LenA?+?x =??n*R;　　LenA = n*R -x; ?亦可以看成 LenA = m*R + y

4.求有環(huán)單鏈表的鏈表長(zhǎng)

?　　上述2中求出了環(huán)的長(zhǎng)度；3中求出了連接點(diǎn)的位置，就可以求出頭結(jié)點(diǎn)到連接點(diǎn)的長(zhǎng)度。兩者相加就是鏈表的長(zhǎng)度。

來(lái)源：?http://www.cnblogs.com/xudong-bupt/p/3667729.html

null

轉(zhuǎn)載于:https://www.cnblogs.com/zhxshseu/p/f8973e488b1e794e4312d1915ba90381.html

總結(jié)

以上是生活随笔為你收集整理的Linked List Cycle的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。