142. Linked List Cycle II
給定一個鏈表的頭節點 head，返回環開始的節點。如果沒有環，返回 null。
如果在鏈表中存在某個節點，可以通過不斷地跟隨下一個指針再次到達該節點，則鏈表中存在環。在內部，pos 用於表示尾部的下一個指針連接到的節點的索引（0 索引）。如果沒有環，pos 為 -1。注意，pos 並不作為參數傳遞。
不要修改鏈表。
例如 ：
輸入：head = [3,2,0,-4], pos = 1 輸出：尾部連接到節點索引 1 解釋：鏈表中存在一個環，其中尾部連接到第二個節點。
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from typing import Optional
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
slow = head
fast = head
# Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Find the start of the cycle
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
19.00MB, 42ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
ListNode* slow = head;
ListNode* fast = head;
// Detect cycle
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
// If no cycle is found, return nullptr
if (fast == nullptr || fast->next == nullptr) {
return nullptr;
}
// Find the start of the cycle
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
10.08MB, 6ms
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
if (head === null || head.next === null) {
return null;
}
let slow = head;
let fast = head;
// Detect cycle
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
break;
}
}
// If no cycle is found, return null
if (fast === null || fast.next === null) {
return null;
}
// Find the start of the cycle
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
};
53.09MB, 69ms
