黑洞入口:142. 環形鏈表 II - 力扣(LeetCode) (leetcode-cn.com)
給定一個鏈表的頭節點 head ,返回鏈表開始入環的第一個節點。 如果鏈表無環,則返回 null。
如果鏈表中有某個節點,可以通過連續跟蹤 next 指針再次到達,則鏈表中存在環。 為了表示給定鏈表中的環,評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。如果 pos 是 -1,則在該鏈表中沒有環。注意:pos 不作為參數進行傳遞,僅僅是為了標識鏈表的實際情況。
不允許修改 鏈表。
示例 1:
輸入:head = [3,2,0,-4], pos = 1
輸出:返回索引為 1 的鏈表節點
解釋:鏈表中有一個環,其尾部連接到第二個節點。
示例 2:
輸入:head = [1,2], pos = 0
輸出:返回索引為 0 的鏈表節點
解釋:鏈表中有一個環,其尾部連接到第一個節點。
示例 3:
輸入:head = [1], pos = -1
輸出:返回 null
解釋:鏈表中沒有環。
提示:
鏈表中節點的數目范圍在范圍 [0, 104] 內
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引
這個題的寫法有2種(題解也是這么說的,哈哈),第一種是用hashset,這種比較簡單,我就不在這里細說了,另外一種用快慢指針我覺得可以說一下,我們先思考一下這么判斷有環的,這個就可以以我們高中做個的物理和數學題,就是在一個操場跑道,2個人起點相同,速度不同,問在操場多少米會相遇,通過這個我們可以知道,只要在環力,速度不同的2個,肯定會相遇,所以在這里我們就可以用一個fast和slow指針,一個一次走一個結點,一個一次走兩個結點,當fast和slow相遇了有什么用呢?只是單純的告訴我們有環嗎,no,no,no,肯定不是這樣的,在這里我們可以假設一下
slow走過的結點:x+y fast走過的結點:x+y+n(y+z)(n是代表fast在環里面走過的圈數)
在這里我們可以知道slow*2=fast,通過上面的式子化簡得x+y=n(y+z),x=(n-1)(y+z)+z,這里的n肯定是>1的(因為fast肯定走了一圈才能遇到slow,所以不用擔心自己化簡這樣有問題),細心的大佬肯定發現了這里的y+z不就是環的一圈嗎,寫成x=n+z不就行了(這就糊涂了呀,n是圈數,這里用的的結點數哦),我們這里的y+z可以思考一下,我們知道這個y+z是一圈,所以當我們有一個指針走的結點數是x,有一個指針走的結點數是(n-1)(y+z)+z,是不是他們就肯定會相等呢,相等的時候的結點是不是肯定就是環的入口,這不就是我們想要的嗎,所以這里我們只需要設置2個指針變量,當有環的時候,一個指向頭節點,一個指向相遇的結點,直到這2個指針相等,就是環的入口,在這里還有一個小問題,為什么slow走過的結點不是x+y+m(y+z),m為slow走過的圈數,這個問題可以留給各位自己去求證一下,如果寫出來證明過程可寫在評論里面
代碼如下:
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; if(fast.next != null) fast = fast.next.next; if(fast == slow){ ListNode r = head; while(r != fast){ r = r.next; fast = fast.next; } return fast; } } return null; } }
當菜鳥的第10天 2022-05-03
浙公網安備 33010602011771號