Linked List Patterns

EasyMedium

Imagine a chain of people, each holding the hand of the person behind them. Nobody can see more than one step ahead. To reverse the chain, each person must let go of one hand and grab a different one — carefully, so nobody gets lost. That is linked list manipulation: pointer surgery where one wrong reassignment severs the entire structure.

Frequency: Very High

|top tech companies

Interactive: watch a 5-node linked list get reversed step by step with prev/curr/next pointers

Readyprev • curr • next

Original list: 1 → 2 → 3 → 4 → 5. Press Start to reverse it step by step.

How to Learn This Page (Student Guide)

Here's the recommended flow:

1.Start with Why This Pattern Exists to understand why linked list pointer manipulation is a distinct skill from array processing.
2.Study Pattern Recognition and the decision flowchart. In an interview, instantly knowing whether to use reversal, fast/slow, or dummy head is the key differentiator.
3.Memorize the Core Templates — reversal, merge with dummy head, and fast/slow. These three cover 90% of linked list interview questions.
4.Work through the 5 Worked Examples in order. Each builds on the previous techniques and the final two combine multiple patterns.

Think of linked list problems like untangling a chain in the dark — you can only feel one link at a time. The three-pointer pattern (prev, curr, next) is your flashlight: it lets you safely rewire one connection without losing the rest of the chain.

Why This Pattern Exists

Linked list problems are fundamentally different from array problems. With arrays, you have random access — jump to any index in O(1). With linked lists, you can only traverse node by node. This constraint creates an entirely different class of problems where pointer manipulation is everything.

The Core Challenge

Consider reversing an array: arr.reverse() or swap from both ends with random access — trivial. Now try reversing a singly linked list. You cannot go backward. You cannot index into the middle. You must carefully redirect .next pointers one at a time, ensuring you never lose the reference to the rest of the list. One wrong assignment and half your list is garbage collected.

the_fundamental_difference.py

1# ARRAY: Reversing is trivial — O(n) with random access
2arr = [1, 2, 3, 4, 5]
3arr.reverse()  # Done. [5, 4, 3, 2, 1]
4
5# LINKED LIST: No random access. Must redirect pointers carefully.
6# If you do: node.next = prev  (reverse the link)
7# You just LOST the reference to the rest of the list!
8# That's why you need THREE pointers: prev, curr, next_node
9
10# Wrong (loses the list):
11# curr.next = prev   # <-- rest of list is now unreachable!
12
13# Correct (save next before overwriting):
14# next_node = curr.next   # Save the rest of the list
15# curr.next = prev        # NOW safe to reverse the link
16# prev = curr             # Advance prev
17# curr = next_node        # Move to the saved next node

Five Sub-Patterns That Solve Everything

Almost every linked list interview problem uses one or more of these five techniques. Master them, and you can solve any linked list question thrown at you.

1. Reversal

Three-pointer technique (prev, curr, next) to reverse all or part of a list.

2. Fast / Slow

Two pointers at different speeds for cycle detection, finding the middle, etc.

3. Dummy Head

Sentinel node that eliminates edge cases when building or merging lists.

4. Two-Pointer Traversal

Two pointers on different lists that converge (intersection, merge).

5. Combination

Hard problems that chain 2-3 techniques together (reorder list, sort list).

The Unifying Principle

Every linked list pattern exists because you cannot go backward in a singly linked list. Reversal gives you backward access. Fast/slow gives you positional information without counting. Dummy head handles the “no previous node” edge case at the head. These are all workarounds for the same fundamental constraint: sequential, forward-only access.

Now that you understand the five sub-patterns, the next skill is recognizing which one to use. The signals and decision flowchart below will help you pick the right technique within 30 seconds.

Pattern Recognition

The first step to solving any linked list problem is identifying which sub-pattern applies.

Use this pattern when you see...

"Reverse a linked list" or "reverse in k-groups"
"Detect if a linked list has a cycle"
"Find the middle node of a linked list"
"Merge two sorted linked lists"
"Add two numbers represented as linked lists"
"Find the intersection of two linked lists"
"Reorder list (interleave front and back)"
"Check if a linked list is a palindrome"

Decision Flowchart

Linked List Problems

Reverse Linked List (iterative & recursive)
Merge Two Sorted Lists
Linked List Cycle / Cycle II
Add Two Numbers
Reorder List / Palindrome Linked List

NOT Linked List Pattern Problems

LRU Cache (uses hash map + doubly linked list — design pattern)
Flatten a Multilevel Doubly Linked List (DFS / stack)
Copy List with Random Pointer (hash map cloning)
Sort a linked list (merge sort — divide & conquer)
Reverse Nodes in k-Group (combines reversal + recursion)

You can now recognize linked list problems. Next, memorize these three reusable templates — they are the building blocks for every worked example that follows.

Core Templates — Reusable Code

These three templates cover the vast majority of linked list interview problems.

1. Iterative Reversal (Three Pointers)

reverse_linked_list_template

1def reverse_list(head):
2    """Reverse a singly linked list iteratively."""
3
4    # SECTION 1: INITIALIZATION
5    # prev starts as None — the reversed list is empty.
6    # curr starts at head — the first node to process.
7    prev = None
8    curr = head
9
10    # SECTION 2: MAIN LOOP — process each node
11    while curr:
12        # SECTION 3: THE THREE-STEP DANCE
13        next_node = curr.next  # 1. Save the next node (don't lose it!)
14        curr.next = prev       # 2. Reverse the link (point backward)
15        prev = curr            # 3a. Advance prev to current node
16        curr = next_node       # 3b. Advance curr to saved next
17
18    # SECTION 4: prev is now the new head (last node processed)
19    return prev

2. Merge with Dummy Head

merge_with_dummy_head_template

1def merge_two_lists(l1, l2):
2    """Merge two sorted linked lists using a dummy head."""
3
4    # SECTION 1: DUMMY HEAD — eliminates the 'first node' edge case
5    dummy = ListNode(0)  # Value doesn't matter
6    tail = dummy          # tail tracks the end of our merged list
7
8    # SECTION 2: COMPARISON LOOP — pick the smaller node each time
9    while l1 and l2:
10        if l1.val <= l2.val:
11            tail.next = l1   # Append l1's node
12            l1 = l1.next     # Advance l1
13        else:
14            tail.next = l2   # Append l2's node
15            l2 = l2.next     # Advance l2
16        tail = tail.next     # Move tail forward
17
18    # SECTION 3: APPEND REMAINDER — one list might still have nodes
19    tail.next = l1 if l1 else l2
20
21    # SECTION 4: RETURN — skip the dummy node
22    return dummy.next

3. Fast / Slow Pointer

fast_slow_pointer_template

1def find_middle(head):
2    """Find the middle node using fast/slow pointers."""
3
4    # SECTION 1: Both start at head
5    slow = head
6    fast = head
7
8    # SECTION 2: Fast moves 2x speed — when fast reaches the end,
9    # slow is at the middle (travels half the distance)
10    while fast and fast.next:
11        slow = slow.next        # 1 step
12        fast = fast.next.next   # 2 steps
13
14    # SECTION 3: slow is now at the middle
15    # Odd list [1,2,3,4,5]: slow = 3 (exact middle)
16    # Even list [1,2,3,4]: slow = 3 (second of two middles)
17    return slow
18
19def has_cycle(head):
20    """Detect cycle using Floyd's tortoise and hare."""
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  # They met inside the cycle
27    return False  # fast reached the end — no cycle

How to Apply These Templates

Reversal: Whenever you need to access nodes in reverse order — reverse all or part of the list. Also used for palindrome checks (reverse second half and compare).
Dummy Head: Whenever you are building a new list node-by-node — merge, partition, add numbers. The dummy removes if head == null checks.
Fast/Slow: Whenever you need positional info without counting — middle node, cycle detection, nth-from-end. The speed difference encodes distance.

Detailed Reversal Walkthrough

Step through the iterative reversal of 1 → 2 → 3 → 4 → 5. Watch how prev, curr, and next pointers move at each iteration.

1 / 6

Initialize: prev = null, curr = node 1, next = null. We are about to process the first node. The reversed portion is empty.

prev=null, curr=1, next=null

Templates memorized? Now let's apply them to real interview problems. Each example includes a step-by-step dry run, full code in three languages, and the key insight that interviewers look for.

Worked Examples

Reverse Linked List

EasyLC 206

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Approach: Iterative Three-Pointer

This is the canonical linked list reversal — the foundation for dozens of harder problems. The idea is simple: walk through the list and redirect each .next pointer to point backward instead of forward. The three pointers (prev, curr, next_node) ensure we never lose access to the rest of the list.

Step	prev	curr	next	Action
0	null	1	—	Initialize
1	1	2	2	1.next = null. Advance prev=1, curr=2
2	2	3	3	2.next = 1. Advance prev=2, curr=3
3	3	4	4	3.next = 2. Advance prev=3, curr=4
4	4	5	5	4.next = 3. Advance prev=4, curr=5
5	5	null	null	5.next = 4. Done! Return prev = 5

reverse_linked_list.py

1class Solution:
2    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        prev = None
4        curr = head
5
6        while curr:
7            next_node = curr.next  # Save next
8            curr.next = prev       # Reverse the link
9            prev = curr            # Move prev forward
10            curr = next_node       # Move curr forward
11
12        return prev  # prev is the new head
13
14    # --- Recursive approach (alternative) ---
15    def reverseListRecursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
16        # Base case: empty list or single node
17        if not head or not head.next:
18            return head
19
20        # Recurse: reverse the rest of the list
21        new_head = self.reverseListRecursive(head.next)
22
23        # head.next is the last node in the reversed portion
24        # Make it point back to us
25        head.next.next = head
26        head.next = None  # Break the forward link
27
28        return new_head  # Propagate the new head up

Time

O(n)

Visit each node once

Space (iterative)

O(1)

Only 3 pointers

Space (recursive)

O(n)

Call stack depth

Key Insight

The iterative approach is preferred in interviews because it uses O(1) space. The recursive approach is elegant but uses O(n) stack space. Know both — interviewers often ask you to implement whichever one you didn't choose first.

Merge Two Sorted Lists

EasyLC 21

Problem

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Approach: Dummy Head + Comparison

Use a dummy head node so we never need special-case logic for the first appended node. Then compare the heads of both lists, append the smaller one, and advance that list's pointer. When one list is exhausted, attach the remainder of the other (already sorted, already linked).

Step	l1	l2	Compare	Merged so far
0	1→2→4	1→3→4	—	dummy
1	2→4	1→3→4	1 ≤ 1	1
2	2→4	3→4	1 ≤ 2	1→1
3	4	3→4	2 ≤ 3	1→1→2
4	4	4	3 ≤ 4	1→1→2→3
5	null	4	4 ≤ 4	1→1→2→3→4
6	null	null	append remaining	1→1→2→3→4→4

merge_two_sorted_lists.py

1class Solution:
2    def mergeTwoLists(self, l1: Optional[ListNode],
3                      l2: Optional[ListNode]) -> Optional[ListNode]:
4        dummy = ListNode(0)
5        tail = dummy
6
7        while l1 and l2:
8            if l1.val <= l2.val:
9                tail.next = l1
10                l1 = l1.next
11            else:
12                tail.next = l2
13                l2 = l2.next
14            tail = tail.next
15
16        # Append whichever list still has nodes
17        tail.next = l1 if l1 else l2
18
19        return dummy.next
20
21# Why dummy head?
22# Without it, you need: if not head: head = node; else: tail.next = node
23# With it, EVERY append is just: tail.next = node; tail = tail.next
24# Cleaner code = fewer bugs in an interview.

Time

O(n + m)

Each node visited once

Space

O(1)

Reusing existing nodes

Key Insight

The dummy head technique is the #1 linked list trick to memorize. It eliminates the “is this the first node?” check that causes bugs under interview pressure. You will use it in merge, partition, add numbers, and many other problems.

Add Two Numbers

MediumLC 2

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

Approach: Digit-by-Digit Addition with Carry

Since digits are in reverse order (least significant first), we can add them directly left to right, exactly like grade-school addition. Keep a carry variable. The key edge case: when both lists are exhausted but carry is 1 (e.g., 999 + 1 = 1000), we need an extra node.

Dry Run: 342 + 465 = 807 (stored as 2→4→3 + 5→6→4)

Step	l1 digit	l2 digit	carry in	sum	new digit	carry out
1	2	5	0	7	7	0
2	4	6	0	10	0	1
3	3	4	1	8	8	0

Result: 7 → 0 → 8 = 807

add_two_numbers.py

1class Solution:
2    def addTwoNumbers(self, l1: Optional[ListNode],
3                      l2: Optional[ListNode]) -> Optional[ListNode]:
4        dummy = ListNode(0)
5        curr = dummy
6        carry = 0
7
8        # Continue while either list has digits OR there's a carry
9        while l1 or l2 or carry:
10            val = carry
11            if l1:
12                val += l1.val
13                l1 = l1.next
14            if l2:
15                val += l2.val
16                l2 = l2.next
17
18            carry, digit = divmod(val, 10)  # carry = val // 10, digit = val % 10
19            curr.next = ListNode(digit)
20            curr = curr.next
21
22        return dummy.next
23
24# Edge case: 999 + 1 = 1000
25# l1: 9->9->9, l2: 1
26# Step 1: 9+1+0=10 → digit=0, carry=1
27# Step 2: 9+0+1=10 → digit=0, carry=1
28# Step 3: 9+0+1=10 → digit=0, carry=1
29# Step 4: 0+0+1=1  → digit=1, carry=0  ← "or carry" catches this!
30# Result: 0->0->0->1 = 1000

Time

O(max(n, m))

Process all digits

Space

O(max(n, m))

New list for result

Common Mistake

Forgetting the or carry in the while condition is the #1 bug on this problem. When both lists are exhausted but carry = 1, you need one more node. Test with 999 + 1 to verify your solution handles this.

Intersection of Two Linked Lists

EasyLC 160

Problem

Given the heads of two singly linked lists, return the node at which the two lists intersect. If they do not intersect, return null.

Approach: Two-Pointer Redirect

The elegant insight: if pointer A walks through list A then list B, and pointer B walks through list B then list A, they both travel the same total distance: (length_A + length_B). They will reach the intersection node at the same time on their second pass. If no intersection exists, both reach null simultaneously.

List A: a1 → a2 → c1 → c2 → c3 (length: 2 unique + 3 shared = 5)

List B: b1 → b2 → b3 → c1 → c2 → c3 (length: 3 unique + 3 shared = 6)

pA travels: a1, a2, c1, c2, c3, b1, b2, b3, c1 (2+3+3 = 8 steps)

pB travels: b1, b2, b3, c1, c2, c3, a1, a2, c1 (3+3+2 = 8 steps)

Both arrive at c1 after 8 steps!

intersection_two_linked_lists.py

1class Solution:
2    def getIntersectionNode(self, headA: ListNode,
3                            headB: ListNode) -> Optional[ListNode]:
4        pA, pB = headA, headB
5
6        # When a pointer reaches the end, redirect to the OTHER list's head.
7        # Both pointers travel (lenA + lenB) total steps.
8        # If they intersect, they meet at the intersection node.
9        # If not, both reach None at the same time.
10        while pA != pB:
11            pA = pA.next if pA else headB
12            pB = pB.next if pB else headA
13
14        return pA  # Either the intersection node or None
15
16# Why this works:
17# pA travels: lenA + lenB nodes total
18# pB travels: lenB + lenA nodes total
19# Same total distance → they reach the intersection simultaneously
20# If no intersection: both reach null after lenA + lenB steps

Time

O(n + m)

Each pointer traverses both lists

Space

O(1)

Just two pointers

Key Insight

The mathematical guarantee is what makes this beautiful: both pointers travel a + b + c nodes (where a and b are unique lengths, c is shared length). Equal distances at equal speeds means simultaneous arrival. This is an O(1) space solution that avoids counting lengths or using hash sets.

Reorder List

MediumLC 143

Problem

Given the head of a singly linked list L: L0 → L1 → … → Ln, reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Approach: Three-Phase Technique

This problem is the “boss fight” of linked list patterns — it combines three techniques in one problem:

Phase 1 — Find middle: Use fast/slow pointers to split the list into two halves.
Phase 2 — Reverse: Reverse the second half so we can interleave from both ends.
Phase 3 — Merge: Interleave nodes from the first and reversed second halves.

Dry Run: 1 → 2 → 3 → 4 → 5

Phase 1: slow=3, fast=5 → split at 3: first=[1,2,3], second=[4,5]

Phase 2: Reverse [4,5] → [5,4]

Phase 3: Interleave [1,2,3] and [5,4]:

1 → 5 → 2 → 4 → 3

Result: 1 → 5 → 2 → 4 → 3

reorder_list.py

1class Solution:
2    def reorderList(self, head: Optional[ListNode]) -> None:
3        if not head or not head.next:
4            return
5
6        # ---- PHASE 1: Find middle using fast/slow ----
7        slow, fast = head, head
8        while fast.next and fast.next.next:
9            slow = slow.next
10            fast = fast.next.next
11        # slow is at the middle (end of first half)
12
13        # ---- PHASE 2: Reverse the second half ----
14        second = slow.next  # Start of second half
15        slow.next = None    # Cut the list in two
16        prev = None
17        while second:
18            nxt = second.next
19            second.next = prev
20            prev = second
21            second = nxt
22        second = prev  # prev is the new head of reversed second half
23
24        # ---- PHASE 3: Merge / interleave the two halves ----
25        first = head
26        while second:
27            tmp1, tmp2 = first.next, second.next
28            first.next = second    # first -> second
29            second.next = tmp1     # second -> next_first
30            first = tmp1           # Advance first
31            second = tmp2          # Advance second
32
33# Why three phases?
34# - Phase 1 (fast/slow): Gives us the split point in O(n)
35# - Phase 2 (reverse): Without reversal, we can't access Ln, Ln-1
36#   efficiently — singly linked lists don't go backward
37# - Phase 3 (merge): Interleave nodes from both halves
38# Total: O(n) time, O(1) space — optimal

Time

O(n)

Three linear passes

Space

O(1)

In-place rearrangement

Key Insight

This problem tests whether you know all three core linked list techniques AND can combine them. Interviewers love it because it reveals depth of understanding. If you can explain why you need each phase (not just what each does), you demonstrate strong linked list mastery.

Interviewer's Perspective

What are interviewers actually testing when they ask linked list problems?

1. Pointer Manipulation Under Pressure

Linked list problems are fundamentally about pointer manipulation. Can you track three pointers simultaneously? Can you redirect links without losing references? Can you handle null edge cases? This is core systems programming skill.

2. Edge Case Awareness

The best candidates proactively mention: empty list, single node, even vs odd length, lists of different lengths, cycle vs no cycle. These edge cases are where bugs hide.

3. Space Optimization

Many linked list problems have an O(n) space solution (copy to array, do operations, rebuild). Interviewers want the O(1) space in-place solution. They want to see that you can work within the constraints of the data structure rather than converting to something easier.

4. Technique Composition

Problems like Reorder List and Palindrome Linked List require combining multiple techniques. This tests whether you see linked list patterns as composable building blocks rather than isolated tricks. The candidate who says “I will find the middle with fast/slow, reverse the second half, then merge” demonstrates architectural thinking.

Edge Cases & Follow-ups

Critical Edge Cases

• Empty list (null head): Always check if not head first. Dereferencing null is the #1 linked list runtime error.
• Single node: A list with one node is already reversed, already a palindrome, has no cycle. Your code must handle this gracefully.
• Even vs odd length: Fast/slow pointer gives different “middle” positions. Test both cases.
• Lists of different lengths: For intersection and merge, one list may be exhausted first. For add-two-numbers, one may have more digits.
• Trailing carry: 999 + 1 = 1000 — the result has one more digit than either input.

Common Follow-up Questions

• “Can you do it recursively?” — Always possible, but costs O(n) stack space. Know both approaches.
• “What if it is a doubly linked list?” — Reversal becomes easier (swap prev/next at each node). Intersection uses backward traversal.
• “What if the numbers are stored in forward order?” (Add Two Numbers II) — Use a stack or reverse first, then add.
• “Find the start of the cycle, not just detect it.” (Linked List Cycle II) — After detection, reset one pointer to head and advance both at speed 1.
• “Can you reverse in groups of k?” — Apply the reversal template to k nodes at a time, chain the groups together.

Linked list patterns connect to these other topics. Master them next.

Two Pointers

Fast/slow on linked lists is a variant of two pointers. The array version covers opposite-direction and same-direction variants.

BFS / DFS on Trees

Trees are linked lists that branch. Many tree traversal patterns (especially recursive ones) build on linked list recursion fundamentals.

Linked Lists Concept

Review the fundamentals — singly vs doubly linked, memory layout, and the basic operations that these patterns build upon.

Divide and Conquer

Merge sort on linked lists is a divide-and-conquer application that uses fast/slow (to split) and merge (to combine) — two core linked list techniques.

🏋️