NUHMAN.com

Introduction

LeetCode 141: Linked List Cycle asks us to determine whether a linked list contains a cycle. A cycle occurs when a node’s next pointer points back to a previous node in the list, creating an infinite loop.

This is a classic linked list problem, often solved using Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare approach.

Problem Statement

Given the head of a singly linked list, return true if there is a cycle in the linked list. Otherwise, return false.

Example

go

Input: head = [3,2,0,-4] (tail connects to node index 1)
Output: true
go

Input: head = [1,2] (tail connects to node index 0)
Output: true
go

Input: head = [1] (no cycle)
Output: false

Approach

✅ Floyd’s Cycle Detection (Fast and Slow Pointers)

We use two pointers:

• Slow pointer moves one step at a time.
• Fast pointer moves two steps at a time.

If there's a cycle, the fast pointer will eventually meet the slow pointer.

If there's no cycle, the fast pointer will reach the end (nil).

Go Implementation

go

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }

    return false
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• n is the number of nodes in the linked list.
• We only use two pointers—no extra space is needed.

Why This Works

• If a cycle exists, the fast pointer will eventually “lap” the slow pointer.
• If there's no cycle, the fast pointer will reach the end (nil).

This technique is both efficient and elegant, and it avoids extra memory usage compared to using a map or set.

Edge Cases

• Empty list (head == nil) → returns false
• Single node with no cycle → returns false
• Single node that links to itself → returns true

Conclusion

LeetCode 141: Linked List Cycle is a staple in algorithm interviews and tests your ability to work with pointers in linked lists. Using the fast and slow pointer method keeps your solution optimal and elegant, a vital trick for tackling many other problems in this domain.