EasyBlind75Linked ListTwo Pointers

Linked List Cycle

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

Examples

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

There is a cycle where the tail connects to the 1st node.

Input
head = [1,2], pos = -1
Output
false

There is no cycle in the linked list.

Constraints

  • •The number of 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.

Approaches

Traverse the list and store visited nodes in a hash set.

CodeT: O(n) | S: O(n)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head):
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

Use two pointers moving at different speeds. If they meet, there's a cycle.

CodeT: O(n) | S: O(1)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head):
    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

Same Floyd's algorithm with a cleaner implementation.

Diagram

3->2->0->-4->2 (cycle at pos=1) slow=3,fast=3 slow=2,fast=0 slow=0,fast=2 slow=-4,fast=-4 -> meeting point -> True
CodeT: O(n) | S: O(1)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Complexity Comparison

Hash Set
T: O(n)S: O(n)

Traverse the list and store visited nodes in a hash set.

Floyd's Tortoise and Hare
T: O(n)S: O(1)

Use two pointers moving at different speeds. If they meet, there's a cycle.

Floyd's Algorithm - Clean
T: O(n)S: O(1)

Same Floyd's algorithm with a cleaner implementation.

Common Mistakes

Not checking if fast or fast.next is None before advancing

Using the node value instead of node reference for comparison

Forgetting that the cycle might not exist

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems