142. 環形連結清單 II
- 題目
- 題解一：快慢指針
- 題解二：哈希表
題目
給定一個連結清單的頭節點 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 或者連結清單中的一個有效索引
進階：你是否可以使用 O(1) 空間解決此題？
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
題解一：快慢指針
算是環形連結清單一的那道題的進階
在環形連結清單一的基礎上，傳回環的開始節點
在環存在的情況下，進行判斷傳回。
以下文字來自力扣官網：
我們使用兩個指針，fast 與 slow。它們起始都位于連結清單的頭部。随後，slow 指針每次向後移動一個位置，而fast 指針向後移動兩個位置。如果連結清單中存在環，則fast 指針最終将再次與 slow 指針在環中相遇。
如下圖所示，設連結清單中環外部分的長度為 aa。slow 指針進入環後，又走了 bb 的距離與 fast 相遇。此時，fast 指針已經走完了環的 nn 圈，是以它走過的總距離為 a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc。
根據題意，任意時刻，fast 指針走過的距離都為 slow 指針的 2 倍。是以，我們有
a+(n+1)b+nc=2(a+b) \implies a=c+(n-1)(b+c)
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量關系，我們會發現：從相遇點到入環點的距離加上 n-1n−1 圈的環長，恰好等于從連結清單頭部到入環點的距離。
是以，當發現 slow 與 fast 相遇時，我們再額外使用一個指針 ptr。起始，它指向連結清單頭部；随後，它和slow 每次向後移動一個位置。最終，它們會在入環點相遇。
作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null){//一、前提
return head;
}
ListNode slowPtr=head,fastPtr=head;//二、聲明
boolean loopExists=false;
while(fastPtr.next!=null && fastPtr.next.next!=null){
slowPtr=slowPtr.next;
fastPtr=fastPtr.next.next;
if(slowPtr==fastPtr){
loopExists=true;
break;//這裡一定要break結束。因為不用就會時間溢出
}
}
if(loopExists){//環存在的情況
slowPtr=head;
while(slowPtr!=fastPtr){//這裡要用whlie，而不是if
slowPtr=slowPtr.next;
fastPtr=fastPtr.next;
}
return slowPtr;//傳回環的開始節點
}
return null;//環不存在
}
} 題解二：哈希表
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null){//一、前提
return head;
}
ListNode pos=head;
Set<ListNode> visited =new HashSet <ListNode>();
while(pos!=null){
if(visited.contains(pos)){//注意格式。這個用法就很友善
return pos;
}
else{
visited.add(pos);
}
pos=pos.next;
}
return null;
}
}