deepSWE.io

Linked List Cycle

Two PointersLinked List

15 min

Problem Statement

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.

Examples

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

There is a cycle where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2,3,4,5], pos = -1

Output: false

No cycle exists - the linked list ends at null (pos = -1 indicates no cycle).

Constraints

• The number of nodes is in the range [0, 10⁴]
• -10⁵ ≤ Node.val ≤ 10⁵
• pos is -1 or a valid index in the linked list

Approach 1: HashSet

The most straightforward approach is to use a hash set to keep track of the nodes we have already visited. We traverse the linked list one node at a time. For each node, we check if it's already in our hash set.

Current Node

Visited Set

Algorithm Steps

Initialize an empty hash set, visited_nodes.
Traverse the list from the head.
If the current node is in visited_nodes, a cycle is found.
Otherwise, add the node to the set and continue.
If the end is reached, no cycle exists.

HashSet Solution


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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        nodes_seen = set()
        current = head
        while current:
            if current in nodes_seen:
                return True
            nodes_seen.add(current)
            current = current.next
        return False

Approach 2: Slow & Fast Pointers

This is the optimal approach, also known as Floyd's Cycle-Finding Algorithm or the "Tortoise and the Hare" algorithm. It uses two pointers that move at different speeds. If there's a cycle, the fast pointer will eventually lap the slow pointer.

Step 0 | Slow: Node 1 | Fast: Node 1

Algorithm Steps

Initialize slow and fast pointers at the head.
Move slow one step and fast two steps.
If the pointers meet, a cycle is detected.
If fast reaches the end, no cycle exists.

Slow & Fast Pointer Solution


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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next
        
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
            
        return True