# 142. Linked List Cycle II

## 題目敘述

Given the `head` of a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to (0-indexed). It is `-1` if there is no cycle. Note that `pos` is not passed as a parameter.

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.
``````

Constraints:

• The number of the nodes in the list is in the range `[0, 10**4]`.
• `-10**5 <= Node.val <= 10**5`
• `pos` is `-1` or a valid index in the linked-list.

Follow up: Can you solve it using `O(1)` (i.e. constant) memory?

## 解法解析

### 解法範例

#### Go

##### Hash Table
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
var visited = make(map[*ListNode]bool)

for node != nil {
if visited[node] {
return node
}
visited[node] = true
node = node.Next
}
return nil
}
``````
##### Floyd's Tortoise and Hare
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return nil
}
if intersect == nil {
return nil
}

ptr2 := intersect
for ptr1 != ptr2 {
ptr1 = ptr1.Next
ptr2 = ptr2.Next
}
return ptr1
}

for hare != nil && hare.Next != nil {
tortoise = tortoise.Next
hare = hare.Next.Next

if hare == tortoise {
}
}
return nil
}
``````

#### JavaScript

##### Hash Table
``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/
var detectCycle = function (head) {
const visited = new Set();

while (node !== null) {
if (visited.has(node)) {
return node;
}
node = node.next;
}
return null;
};
``````
##### Floyd's Tortoise and Hare
``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/
var detectCycle = function (head) {
if (head === null) return null;
if (intersection === null) return null;
ptr2 = intersection;
while (ptr1 !== ptr2) {
ptr2 = ptr2.next;
ptr1 = ptr1.next;
}
return ptr1;
};

const getIntersection = (head) => {

while (hare !== null && hare.next !== null) {
tortoise = tortoise.next;
hare = hare.next.next;

}
return null;
};
``````

#### Kotlin

##### Hash Table
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/

class Solution {
val visited = mutableSetOf<ListNode>()

while (node != null) {
if (visited.contains(node)) {
return node
}
node = node.next
}
return null
}
}
``````
##### Floyd's Tortoise and Hare
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/

class Solution {
private fun getIntersect(head: ListNode): ListNode? {

// A fast pointer will either loop around a cycle and meet the slow
// pointer or reach the `null` at the end of a non-cyclic list.
while (hare != null && hare.next != null) {
tortoise = tortoise?.next
hare = hare?.next?.next
if (tortoise === hare) {
}
}
return null
}

return null
}

// If there is a cycle, the fast/slow pointers will intersect at some
// node. Otherwise, there is no cycle, so we cannot find an entrance to
// a cycle.
val intersect: ListNode = getIntersect(head) ?: return null

// To find the entrance to the cycle, we have two pointers traverse at
// the same speed -- one from the front of the list, and the other from
// the point of intersection.
var ptr2: ListNode = intersect
while (ptr1 !== ptr2) {
ptr1 = ptr1.next
ptr2 = ptr2.next
}
return ptr1
}
}
``````

#### PHP

##### Hash Table
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val) { \$this->val = \$val; }
* }
*/

class Solution
{
/**
* @return ListNode
*/
{
\$visited = [];
}
}
return null;
}
}
``````
##### Floyd's Tortoise and Hare
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val) { \$this->val = \$val; }
* }
*/

class Solution
{
/**
* @return ListNode
*/
{
return null;
}

if (is_null(\$intersect)) {
return null;
}

\$ptr2 = \$intersect;
while (\$ptr1 !== \$ptr2) {
\$ptr1 = \$ptr1->next;
\$ptr2 = \$ptr2->next;
}
return \$ptr1;
}

{

while (!is_null(\$hare) && !is_null(\$hare->next)) {
\$tortoise = \$tortoise->next;
\$hare = \$hare->next->next;
if (\$tortoise === \$hare) {
return \$tortoise;
}
}
return null;
}
}
``````

#### Python

##### Hash Table
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def detectCycle(self, head: ListNode | None) -> ListNode | None:
visited = set()

while node is not None:
if node in visited:
return node
node = node.next

return None
``````
##### Floyd's Tortoise and Hare
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def getIntersect(self, head: ListNode | None) -> ListNode | None:

# A fast pointer will either loop around a cycle and meet the slow
# pointer or reach the `null` at the end of a non-cyclic list.
while hare is not None and hare.next is not None:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:

return None

def detectCycle(self, head: ListNode | None) -> ListNode | None:
return None

# If there is a cycle, the fast/slow pointers will intersect at some
# node. Otherwise, there is no cycle, so we cannot find an entrance to
# a cycle.
if intersect is None:
return None

# To find the entrance to the cycle, we have two pointers traverse at
# the same speed -- one from the front of the list, and the other from
# the point of intersection.
ptr2 = intersect
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next

return ptr1
``````

#### Rust

``````
``````

#### Swift

##### Hash Table
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.next = nil
*     }
* }
*/

class Solution {
func detectCycle(_ head: ListNode?) -> ListNode? {
var visited = [ListNode]()

while node != nil {
if visited.contains(where: {\$0 === node!}) {
return node
}
visited.append(node!)
node = node?.next
}
return nil
}
}
``````
##### Floyd's Tortoise and Hare
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.next = nil
*     }
* }
*/

class Solution {
private func getIntersect(_ head: ListNode?) -> ListNode? {
while hare != nil, hare?.next != nil {
tortoise = tortoise?.next
hare = hare?.next?.next
if tortoise === hare {
}
}
return nil
}

func detectCycle(_ head: ListNode?) -> ListNode? {
return nil
}

if intersect == nil {
return nil
}

var ptr2 = intersect
while ptr1 !== ptr2 {
ptr1 = ptr1?.next
ptr2 = ptr2?.next
}
return ptr1
}
}
``````