# Leetcode --- 141. Linked List Cycle

## [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
### Description:
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.

:::info
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.
:::
:::warning

:::
解法1 (紀錄node)
解法2 (Floyed)
解法3 (Brent)

Q: Floyed省下的記憶體空間好像沒多少耶
Q: Brent反而比Floyed慢耶

### 解法條列
1. 普通解 O(n) 空間O(n)
2. Floyed解 O(n) 空間O(1)
3. Brent解 O(n) 空間O(1)

### 解法細節
解法1:
以dict記錄訪問過的node，若是下一個node有被記錄在dict，則代表有cycle

可以使用技巧(算法)讓空間複雜度

### Python Solution
普通解

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        dict_node = {}
        temp = head
        while(temp):
            if(dict_node.get(temp, False)):
                return True
            dict_node[temp] = True
            temp = temp.next
        return False            

---
Floyed

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if(slow == fast):
                return True
        return False

---
Brent

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if(not head):
            return False
        slow = head
        fast = head
        for i in range(14):
            count = 0
            target = 2**i
            while(count < target):
                fast = fast.next
                count += 1
                if(not fast):
                    return False
                elif(slow == fast):
                    return True
            slow = fast

---

###### tags: `leetcode` `linked list` `easy` `homework`