題目描述
142.環形鏈表 II
給定一個鏈表，回傳鏈表開始入環的第一個節點，如果鏈表無環，則回傳 null，
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，
說明：不允許修改給定的鏈表，
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環，其尾部連接到第二個節點，
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環，其尾部連接到第一個節點，
題目決議
方法一：哈希表
解題思路
首先可以想到的方法就是遍歷鏈表并將遍歷的鏈表Node節點存入哈希表中，若鏈表有環則回傳第一個出現的重復的Node節點，
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode detectCycle(ListNode head) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) {
return curr;
}
visited.add(curr);
curr = curr.next;
}
return null;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)，通過額外空間存盤遍歷節點
方法二：雙指標
解題思路
在上一題環形鏈表中已經提過若鏈表有環的情況，快慢指標會在某個節點相遇，
此時鏈表頭節點到環起始點的距離為x，環起始點到快慢指標相遇節點的距離為y，然后相遇節點再繼續走z的距離回到環起始點，
由于快指標的速度時慢指標的兩倍，所以快指標追上慢指標必然比慢指標多走一圈，此時慢指標走的路程s = x + y，快指標走的路程f = x + y + z + y，且 f = 2s，所有可以得到 x = z，也就是說頭節點到環起始點的距離等于指標相遇節點到環起始點距離，所以當快慢指標相遇時，指定其中一個指標回到頭節點，并保持相等的速度繼續遍歷直到兩個指標再次相遇則為鏈表環的起始點了，
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (true) {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65510.html
標籤：其他
下一篇：原碼，反碼與補碼