# 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:

``````[3] -> [2] -> [0] -> [4]
^_____________|

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:

``````[1] -> [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:

``````[1]

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, 104].
• -105 <= `Node.val` <= 105
• `pos` is `-1` or a valid index in the linked-list.

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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None ''' Set ''' class Solution: def hasCycle(self, head: ListNode) -> bool: seen = set() while head != None: if head not in seen: seen.add(head) head = head.next else: return True return False ''' Two pointers ''' class Solution: def hasCycle(self, head: ListNode) -> bool: p1 = p2 = head while p2 is not None and p2.next is not None: p1 = p1.next p2 = p2.next.next if p1 == p2: return True return False``````