Linked List Fundamentals

A Linked List is a linear data structure where elements (called nodes) are not stored contiguously in memory. Instead, each node is a separate object containing a value and a pointer (or reference) to the next node in the sequence. Traversal must be done sequentially starting from the head node.

By manipulating pointer links directly, linked lists allow for $O(1)$ insertions and deletions, but searching requires $O(N)$ linear scans.

The Core Concept: Linked List Cycle Detection

To understand this concept deeply, let's explore Linked List Cycle.

Problem Statement: Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle if some node in the list can be reached again by continuously following the next pointer.

Naive Brute Force — $O(N)$ Time & $O(N)$ Space

A straightforward approach is to traverse the list and keep track of every node we visit in a Hash Set. If we ever encounter a node that is already in the set, a cycle exists:

def hasCycleNaive(head: ListNode) -> bool:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

While this runs in $O(N)$ time, it requires $O(N)$ auxiliary space to store visited nodes, which can be problematic for very large lists in memory-constrained environments.

Floyd's Cycle Detection (Fast & Slow Pointers) — $O(N)$ Time & $O(1)$ Space

We can optimize the space complexity to $O(1)$ using the Fast & Slow pointer (or "tortoise and hare") technique:

Initialize two pointers at the head of the list: slow and fast.
Move slow forward by 1 step at a time, and fast forward by 2 steps at a time.
If there is no cycle, fast will reach the end of the list (None).
If there is a cycle, the fast pointer will loop around and eventually "lap" the slow pointer, meeting it at the exact same node.

This pointer chase detects cycles using zero extra memory.

Step-by-Step Traversal

Let's trace the algorithm on a list with 4 nodes where node 4 points back to node 2 (a cycle).

Step 1: Initialization

Both pointers, slow and fast, start at the head of the list (Node 1).

SETInitialize fast pointer at the head of the list.1 / 14

∅

slow

fast

head

scroll to zoom · drag to pan

114

Step 2: First Advance

We move slow 1 step forward to Node 2.
We move fast 2 steps forward to Node 3.

MOVEAdvance fast pointer by 2 step1 / 11

∅

slow

fast

head

scroll to zoom · drag to pan

111

Since they are at different nodes, we continue.

COMPARECheck if slow and fast pointers have met.1 / 10

∅

slow

fast

head

scroll to zoom · drag to pan

110

Step 3: Second Advance

We move slow 1 step forward to Node 3.
We move fast 2 steps forward. Node 3 moves to Node 4, and then back to Node 2 due to the cycle.

MOVEAdvance fast pointer by 2 step1 / 7

∅

slow

fast

head

scroll to zoom · drag to pan

Since they are at different nodes, we continue.

COMPARECheck if slow and fast pointers have met.1 / 6

∅

slow

fast

head

scroll to zoom · drag to pan

Step 4: Third Advance

We move slow 1 step forward to Node 4.
We move fast 2 steps forward. Node 2 moves to Node 3, and then to Node 4.

MOVEAdvance fast pointer by 2 step1 / 3

∅

slow

fast

head

scroll to zoom · drag to pan

Both pointers are now at Node 4!

COMPARECheck if slow and fast pointers have met.1 / 2

∅

slow

fast

head

scroll to zoom · drag to pan

Step 5: Cycle Detected

Since slow and fast pointers have met, we confirm a cycle exists and return True.

FOUNDCycle detected! The fast pointer has lapped the slow pointer. Return True.1 / 1

∅

slow & fast

scroll to zoom · drag to pan

Code Implementation

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
        
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next          # Move slow 1 step
        fast = fast.next.next     # Move fast 2 steps
        
        # If the pointers meet, a cycle exists
        if slow == fast:
            return True
            
    return False                  # Fast reached the end, no cycle

Time Complexity: $O(N)$ — where $N$ is the number of nodes in the list. If there is a cycle, the pointers will meet in at most one full traversal of the cycle. Space Complexity: $O(1)$ — we only store two pointer variables.

Core Variations

1. Sentinel (Dummy) Node

A helper node inserted at the front of a list to simplify insertions, deletions, and merges by removing edge cases for the list head.

Use when: editing the head of the list or merging lists.
Examples: Merge Two Sorted Lists, Remove Nth Node From End.

2. Middle of Linked List

Find the exact midpoint of a list in a single pass.

Approach: Move slow by 1 step and fast by 2 steps. When fast reaches the end, slow is at the middle.
Example: Middle of the Linked List.

3. Reversing Links In-Place

Iteratively redirecting each node's next pointer backward.

Approach: Maintain three pointers (prev, curr, next_node) to redirect arrows without breaking connections.
Example: Reverse Linked List.

When Do I Use This?

Check for these conditions:

The problem involves a Linked List structure.
You need to detect cycles or find meetings points (use Fast & Slow).
You need to manipulate, divide, or merge nodes in-place without copying values (use Sentinel and Multi-Pointer tracking).

If yes, the Linked List pattern is required.

Practice Problems

Done	Question	Difficulty
	Linked List Cycle	Easy
	Palindrome Linked List	Easy
	Remove Nth Node From End of List	Medium
	Reorder List	Medium
	Reverse Linked List	Easy

Linked List Fundamentals

The Core Concept: Linked List Cycle Detection

Naive Brute Force — O(N)O(N)O(N) Time & O(N)O(N)O(N) Space

Floyd's Cycle Detection (Fast & Slow Pointers) — O(N)O(N)O(N) Time & O(1)O(1)O(1) Space

Step-by-Step Traversal

Step 1: Initialization

Step 2: First Advance

Step 3: Second Advance

Step 4: Third Advance

Step 5: Cycle Detected

Code Implementation

Core Variations

1. Sentinel (Dummy) Node

2. Middle of Linked List

3. Reversing Links In-Place

When Do I Use This?

Practice Problems

Comments

Naive Brute Force — $O(N)$ Time & $O(N)$ Space

Floyd's Cycle Detection (Fast & Slow Pointers) — $O(N)$ Time & $O(1)$ Space