Linked List Cycle

Difficulty: Easy | Acceptance: 54.30% | Paid: No Topics: Hash Table, Linked List, Two Pointers

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.

• Examples
• Constraints
• Brute Force (Nested Iteration)
• Hash Set
• Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Examples

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.

Brute Force (Nested Iteration)

Intuition For every node, traverse the list from the beginning to check if we encounter the current node again. If we do, a cycle exists.

Steps

• Initialize an outer pointer current to the head.
• While current is not null:
  • Initialize an inner pointer checker to the head.
  • While checker is not current:
    • If checker.next is current, we found a cycle, return true.
    • Move checker forward.
  • Move current forward.
• If the loop finishes, return false.

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

class Solution:
    def hasCycle(self, head):
        outer = head
        while outer:
            inner = head
            while inner is not outer:
                if inner.next is outer:
                    return True
                inner = inner.next
            outer = outer.next
        return False

Complexity

• Time: O(n²) - For each node, we traverse the list up to that node.
• Space: O(1) - We only use two pointers.
• Notes: Simple but inefficient for large lists.

Hash Set

Intuition Traverse the list and store every visited node in a hash set. If we encounter a node that is already in the set, it means we have visited it before, indicating a cycle.

Steps

• Initialize an empty set visited.
• Traverse the list with pointer current.
• If current is in visited, return true.
• Add current to visited.
• Move current to current.next.
• If current becomes null, return false.

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

class Solution:
    def hasCycle(self, head):
        visited = set()
        current = head
        while current:
            if current in visited:
                return True
            visited.add(current)
            current = current.next
        return False

Complexity

• Time: O(n) - We traverse the list once.
• Space: O(n) - In the worst case, we store all nodes in the set.
• Notes: Faster time complexity than brute force, but uses extra memory.

Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Intuition Use two pointers, slow and fast. slow moves one step at a time, while fast moves two steps. If there is a cycle, fast will eventually lap slow and they will meet. If there is no cycle, fast will reach the end.

Steps

• Initialize slow and fast to head.
• Loop while fast and fast.next are not null:
  • Move slow one step: slow = slow.next.
  • Move fast two steps: fast = fast.next.next.
  • If slow equals fast, return true.
• If the loop ends, return false.

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

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

Complexity

• Time: O(n) - In the worst case, we traverse the list a constant number of times.
• Space: O(1) - We only use two pointers.
• Notes: Optimal solution with linear time and constant space.