Stacks & Monotonic Stacks Matrix / 2D Arrays

PATTERN 7 OF 22

Linked Lists

Master pointer manipulation with singly linked lists. Learn reversal, dummy head technique, fast/slow pointers, and the two-pointer gap strategy — fundamental building blocks for dozens of interview problems.

Time: O(n)

Space: O(1)

Learn & Reference

Understanding the Pattern

Linked Lists Pattern

A linked list is a linear data structure where each element (node) contains a value and a pointer to the next node. Unlike arrays, linked lists don't support random access — you must traverse from the head to reach any node. This constraint makes pointer manipulation the central skill.

Core Concept

Every node has two fields: val (the data) and next (a pointer to the next node, or null at the end). The list is accessed through a head pointer. Losing the head means losing the entire list.

head → [1] → [2] → [3] → [4] → null

The key insight: you can restructure a linked list in O(1) space by redirecting pointers. No shifting, no copying — just rewiring connections.

Key Techniques

1. Iterative Reversal

The most fundamental linked list operation. Use three pointers: prev, curr, and next. At each step, save curr.next, point curr.next to prev, then advance both pointers.

Before: prev → null, curr → [1] → [2] → [3]
Step 1: null ← [1]  curr → [2] → [3]
Step 2: null ← [1] ← [2]  curr → [3]
Step 3: null ← [1] ← [2] ← [3]  curr → null

Reversal is a subroutine in many problems: reorder list, palindrome check, reverse k-group.

2. Dummy Head (Sentinel Node)

Create a fake node before the real head: dummy.next = head. This eliminates edge cases when the head itself might change (e.g., removing the first node, merging two lists where either could come first).

At the end, return dummy.next as the new head. This tiny trick simplifies code significantly.

3. Fast/Slow Pointers (Floyd's Algorithm)

Two pointers move at different speeds — slow moves one step, fast moves two steps per iteration.

Find the middle node: When fast reaches the end, slow is at the middle. This is O(n) time, O(1) space — no need to count the length first.

Detect a cycle: If there's a cycle, fast will eventually lap slow and they'll meet. If fast reaches null, there's no cycle. This is the foundation of Floyd's cycle detection algorithm.

4. Two-Pointer Gap Technique

To find the nth node from the end in one pass: advance a fast pointer n steps ahead, then move both slow and fast together. When fast reaches the end, slow is at the target.

This avoids needing to know the list length. Combined with a dummy head, it cleanly handles removing the nth node from the end.

5. Merge Technique

Merging two sorted lists: compare the heads of both lists, take the smaller one, advance that pointer. Use a dummy head to avoid special-casing the first node. This is the same merge used in merge sort and is the building block for "merge k sorted lists."

When Linked Lists Fail

You need random access by index → use an array
You need binary search → use an array (no O(1) index access in linked lists)
The data fits in memory and you need cache-friendly traversal → arrays are faster due to spatial locality
You need to traverse backward → use a doubly linked list or reverse first

Common Mistakes

Losing the head reference: If you advance the head pointer during traversal, you can never get back to the start. Always use a separate curr pointer for traversal and keep head (or dummy) untouched
Null pointer errors: Before accessing node.next, check that node is not null. Before accessing node.next.next, check both node and node.next. Fast/slow pointer loops need fast != null && fast.next != null
Forgetting to update next pointers: When removing or inserting a node, every relevant next pointer must be updated. Drawing the before/after diagram on paper prevents most bugs
Off-by-one in the gap technique: To remove the nth node from the end, advance fast by n+1 (or use a dummy head and advance by n). Getting this off by one either skips or includes the wrong node
Creating an unintended cycle: When reversing or reordering, if you don't null-terminate the end of a sublist, you create a cycle that causes infinite loops during traversal

When to Use

Given the head of a linked list in the problem statement

Reverse a list or part of a list

Find the middle node or kth node from the end

Detect or find the start of a cycle

Merge two sorted sequences without extra space

Remove or insert nodes without shifting elements

Reorder or rearrange nodes in-place

The problem involves pointer manipulation or rewiring connections

Palindrome linked list (fast/slow + reverse second half)

LRU Cache or similar ordered data structures (doubly linked list + hash map)

Keywords: linked list, node, pointer, head, next, reverse, cycle, merge, dummy, sentinel

Template

1# --- ListNode Definition ---
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7# --- Reverse a Linked List ---
8def reverse_list(head):
9    prev, curr = None, head
10    while curr:
11        nxt = curr.next  # save next
12        curr.next = prev  # reverse pointer
13        prev = curr       # advance prev
14        curr = nxt        # advance curr
15    return prev  # prev is the new head
16
17# --- Find Middle (for splitting) ---
18def find_middle(head):
19    slow = fast = head
20    while fast and fast.next:
21        slow = slow.next
22        fast = fast.next.next
23    return slow
24
25# --- Merge Two Sorted Lists (Dummy Head) ---
26def merge(l1, l2):
27    dummy = ListNode(0)
28    curr = dummy
29    while l1 and l2:
30        if l1.val <= l2.val:
31            curr.next = l1
32            l1 = l1.next
33        else:
34            curr.next = l2
35            l2 = l2.next
36        curr = curr.next
37    curr.next = l1 or l2
38    return dummy.next

{ }

Syntax Reference

1# --- Python: ListNode Definition ---
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7# --- Traversal ---
8curr = head
9while curr:
10    print(curr.val)
11    curr = curr.next
12
13# --- Insert at head ---
14new_node = ListNode(val)
15new_node.next = head
16head = new_node
17
18# --- Delete next node ---
19if curr.next:
20    curr.next = curr.next.next
21
22# --- Dummy head (sentinel) ---
23dummy = ListNode(0)
24dummy.next = head
25# ... modify list ...
26return dummy.next

📋

Common Recipes

1# --- Reverse a Linked List ---
2def reverse_list(head):
3    prev, curr = None, head
4    while curr:
5        nxt = curr.next
6        curr.next = prev
7        prev = curr
8        curr = nxt
9    return prev
10
11# --- Find Middle Node (slow/fast pointers) ---
12def find_middle(head):
13    slow = fast = head
14    while fast and fast.next:
15        slow = slow.next
16        fast = fast.next.next
17    return slow  # middle node
18
19# --- Detect Cycle (Floyd's Algorithm) ---
20def has_cycle(head):
21    slow = fast = head
22    while fast and fast.next:
23        slow = slow.next
24        fast = fast.next.next
25        if slow == fast:
26            return True
27    return False
28
29# --- Merge Two Sorted Lists (Dummy Head) ---
30def merge_sorted(l1, l2):
31    dummy = ListNode(0)
32    curr = dummy
33    while l1 and l2:
34        if l1.val <= l2.val:
35            curr.next = l1
36            l1 = l1.next
37        else:
38            curr.next = l2
39            l2 = l2.next
40        curr = curr.next
41    curr.next = l1 or l2
42    return dummy.next

O(n)

Complexity

Operation	Time	Space
Access by index	O(n)	O(1)
Search for value	O(n)	O(1)
Insert at head	O(1)	O(1)
Insert at tail (without tail pointer)	O(n)	O(1)
Delete a node (given previous)	O(1)	O(1)
Reverse entire list	O(n)	O(1)
Find middle (fast/slow)	O(n)	O(1)
Detect cycle (Floyd)	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)

Watch Out

✗Losing the head reference: If you advance the `head` pointer during traversal, you can never get back to the start. Always use a separate `curr` pointer for traversal and keep `head` (or `dummy`) untouched
✗Null pointer errors: Before accessing `node.next`, check that `node` is not null. Before accessing `node.next.next`, check both `node` and `node.next`. Fast/slow pointer loops need `fast != null && fast.next != null`
✗Forgetting to update next pointers: When removing or inserting a node, every relevant `next` pointer must be updated. Drawing the before/after diagram on paper prevents most bugs
✗Off-by-one in the gap technique: To remove the nth node from the end, advance `fast` by n+1 (or use a dummy head and advance by n). Getting this off by one either skips or includes the wrong node
✗Creating an unintended cycle: When reversing or reordering, if you don't null-terminate the end of a sublist, you create a cycle that causes infinite loops during traversal

PRACTICE PROBLEMS

Stacks & Monotonic Stacks

Matrix / 2D Arrays