# LeetCode Solution, Easy, 141. Linked List Cycle

## 題目敘述

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

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. Note that `pos` is not passed as a parameter.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

Example 1:

``````Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
``````

Example 2:

``````Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
``````

Example 3:

``````Input: head = [1], pos = -1
Output: false
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 nodesSeen = make(map[*ListNode]bool)
return true
}
}
return false
}
``````
##### Floyd's Cycle Finding Algorithm
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return false
}
for slow != fast {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true
}
``````

#### JavaScript

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

/**
* @return {boolean}
*/
var hasCycle = function (head) {
const nodesSeen = new Set();
return true;
}
}
return false;
};
``````
##### Floyd's Cycle Finding Algorithm
``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {boolean}
*/
var hasCycle = function (head) {
return false;
}
while (slow !== fast) {
if (!fast || !fast.next) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
};
``````

#### Kotlin

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

class Solution {
var nodesSeen = mutableSetOf<ListNode>()
while (node != null) {
if (nodesSeen.contains(node)) {
return true
}
node = node.next
}
return false
}
}
``````
##### Floyd's Cycle Finding Algorithm
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/

class Solution {
if (head == null) return false
while (slow != fast) {
if (fast == null || fast.next == null) return false
slow = slow?.next
fast = fast?.next?.next
}
return true
}
}
``````

#### 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 Boolean
*/
{
\$nodesSeen = [];
return true;
}
}
return false;
}
}
``````
##### Floyd's Cycle Finding Algorithm
``````/**
* Definition for a singly-linked list.
* class ListNode {
*     public \$val = 0;
*     public \$next = null;
*     function __construct(\$val) { \$this->val = \$val; }
* }
*/

class Solution
{
/**
* @return Boolean
*/
{
return false;
}

while (\$slow !== \$fast) {
if (is_null(\$fast) || is_null(\$fast->next)) {
return false;
}
\$slow = \$slow->next;
\$fast = \$fast->next->next;
}
return true;
}
}
``````

#### Python

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

class Solution:
def hasCycle(self, head: ListNode | None) -> bool:
nodes_seen: set[ListNode] = set()
return True
return False
``````
##### Floyd's Cycle Finding Algorithm
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def hasCycle(self, head: ListNode | None) -> bool:
return False
while slow != fast:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next
return True
``````

#### 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 hasCycle(_ head: ListNode?) -> Bool {
var nodesSeen = [ListNode]()
while node != nil {
if nodesSeen.contains(where: {\$0 === node!}) {
return true
}
nodesSeen.append(node!)
node = node?.next
}
return false
}
}
``````
##### Floyd's Cycle Finding Algorithm
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init(_ val: Int) {
*         self.val = val
*         self.next = nil
*     }
* }
*/

class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
guard head != nil else {
return false
}

while slow !== fast {
if fast == nil || fast?.next == nil {
return false
}
slow = slow?.next
fast = fast?.next?.next
}
return true
}
}
``````