How do you solve Linked List Cycle on LeetCode?

Linked List Cycle (LeetCode #141) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using a set to track visited nodes can help identify cycles, but it uses extra space.

What is the brute force solution for Linked List Cycle?

The brute force approach for Linked List Cycle is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach checks each node to see if it has been visited before. If we encounter a node that we've seen before, it means there's a cycle. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Linked List Cycle?

Linked List Cycle uses the following concepts: Hash Table, Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Linked List Cycle?

Clearly explain your thought process before coding. Discuss both brute force and optimal approaches to show depth of understanding. Practice explaining the algorithm as if teaching someone else.

What are common mistakes when solving Linked List Cycle?

Not considering edge cases like an empty list or a single node without a cycle. Confusing the slow and fast pointers' movements.

#141

Linked List Cycle

Easy

Hash TableLinked ListTwo PointersTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses the Floyd's Tortoise and Hare algorithm, where two pointers move at different speeds. If there's a cycle, they will eventually meet.

⚙️

Algorithm

4 steps

1Step 1: Initialize two pointers, slow and fast, both starting at the head of the linked list.
2Step 2: Move slow pointer one step and fast pointer two steps in each iteration.
3Step 3: If slow and fast pointers meet, return true (cycle detected).
4Step 4: If fast pointer reaches the end (null), return false (no cycle).

solution.py15 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def hasCycle(head):
8    slow = head
9    fast = head
10    while fast and fast.next:
11        slow = slow.next
12        fast = fast.next.next
13        if slow == fast:
14            return True
15    return False

ℹ

Complexity note: The time complexity is O(n) because we traverse the list at most twice. The space complexity is O(1) since we only use two pointers.

1Using a set to track visited nodes can help identify cycles, but it uses extra space.
2Floyd's algorithm is efficient as it uses constant space and is faster.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.