Linked List Cycle II (M)
題目
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Follow-up:
Can you solve it without using extra space?
題意
判斷給定鏈表中是否存在環,存在則回傳環的入口結點，
思路
比較簡單的就是將所有遍歷到的結點記錄下來，如果記錄了兩次則說明當前結點就是所求的結點，
同樣可以使用快慢指標的方法：慢指標每次走一步，快指標每次走兩步，如果快指標追上慢指標則說明存在環；當判斷出存在環后，將快指標重新指向頭結點，步進距離改為一個結點，然后使快指標和慢指標同時繼續前進，當兩者再次相遇時，所處結點就是所求入口結點，證明如下：
記第一次相遇時慢指標走過的距離為\(S_1\)，快指標走過的距離為\(S_2\)，那么可得如下方程組：
\[\begin{cases} S_1=x+y \\ S_2=x+y+n*(y+z) \\ S_2=2*S_1 \end{cases} \]化簡后可得：
\[x=(n-1)*(y+z)+z \]說明當快指標重新從A點走到B點時，慢指標從C點出發已經走過了n圈加上z的距離，即也正好落在B點上，因此上述方法能夠正確找到環的入口結點，
代碼實作
Java
Hash
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) {
return head;
}
head = head.next;
}
return null;
}
}
快慢指標
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
JavaScript
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
slow = head
while (slow !== fast) {
slow = slow.next
fast = fast.next
}
return slow
}
}
return null
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/194449.html
標籤：其他
下一篇：容器基礎之（一）容器生態系統