Linked Lists Complete Guide — Every Pattern, Template, and Interview Problem Indexed

Problem Statement#

This guide is the master entry point for the Linked Lists track on webcoderspeed.com. Treat it as a "what to study and in what order" map — every other post in the series implements one of the patterns indexed below.

Constraints (study scope):

• Scope: LeetCode problems 206 through 250, plus a few high-frequency variants
• Difficulty mix: 10 Easy, 25 Medium, 10 Hard (45 total)
• Languages used in solution posts: Python and JavaScript
• Audience: candidates targeting MAANG / FAANG and senior IC interview loops

Input:  any singly or doubly linked list problem
Output: the right pattern + a templated solution in O(n) time / O(1) space when possible

Why This Problem Matters#

Linked list questions are still asked in roughly one out of every three coding rounds at top-tier companies, despite the rise of graph and dynamic programming questions. The reason is simple: linked lists are the cleanest possible test of pointer manipulation, edge-case discipline, and in-place memory reasoning. An interviewer can tell within minutes whether a candidate truly understands references and aliasing, or whether they just memorized a few solutions.

The other reason linked lists matter is that they appear inside almost every system design answer. LRU caches, write-ahead logs, free lists in allocators, schedulers, undo stacks, and adjacency lists in graph engines all rely on doubly linked list mechanics under the hood. If you cannot explain why a doubly linked list with sentinel head and tail enables O(1) move-to-front, you cannot meaningfully discuss caching at the systems level either.

Finally, the patterns generalize. Floyd's tortoise-and-hare technique reappears in cycle detection on functional iterations and in finding the duplicate number in an array. Dummy-head reasoning shows up in segment trees, deque implementations, and even SQL query plan trees. The 7 patterns below are the high-leverage ones — master them and roughly 90% of linked-list interviews collapse to template execution.

The Core Insight#

Almost every linked list problem decomposes into one of seven moves: reverse a segment, walk two pointers at different speeds, insert a dummy head to absorb edge cases, merge sorted lists by linking smaller nodes, rewire pointers in place, clone with auxiliary mapping, or design a custom data structure with sentinel nodes. Memorize the templates, then on every new problem ask: which of the seven am I doing, and on what segment of the list?

Visual Dry Run#

Solution (Optimal)#

The "solution" for a guide post is the template library. These seven snippets, internalized, unlock the entire problem set.

# 1. Reverse a singly linked list (iterative)
class Solution:
    def reverse(self, head):
        prev, curr = None, head
        while curr:
            nxt = curr.next   # save next before overwriting
            curr.next = prev  # rewire backward
            prev, curr = curr, nxt
        return prev
 
    # 2. Fast and slow pointers — find middle (returns second middle for even)
    def find_middle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
 
    # 3. Dummy head — remove nth node from end
    def remove_nth(self, head, n):
        dummy = type(head)(0)
        dummy.next = head
        fast = slow = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next
 
    # 4. Merge two sorted lists
    def merge_two(self, l1, l2):
        dummy = cur = type(l1 or l2)(0)
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next, l1 = l1, l1.next
            else:
                cur.next, l2 = l2, l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next
 
    # 5. In-place rewire — odd indexed nodes first, then even
    def odd_even(self, head):
        if not head:
            return head
        odd, even = head, head.next
        even_head = even
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

// 1. Reverse a singly linked list (iterative)
var reverseList = function(head) {
    let prev = null, curr = head;
    while (curr) {
        const nxt = curr.next;     // save before overwrite
        curr.next = prev;          // rewire backward
        prev = curr;
        curr = nxt;
    }
    return prev;
};
 
// 2. Middle of linked list — fast/slow pointers
var middleNode = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};
 
// 3. Remove Nth from end — dummy head + n-gap
var removeNthFromEnd = function(head, n) {
    const dummy = { val: 0, next: head };
    let fast = dummy, slow = dummy;
    for (let i = 0; i <= n; i++) fast = fast.next;
    while (fast) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
};
 
// 4. Merge two sorted lists
var mergeTwoLists = function(l1, l2) {
    const dummy = { val: 0, next: null };
    let cur = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
        else                  { cur.next = l2; l2 = l2.next; }
        cur = cur.next;
    }
    cur.next = l1 || l2;
    return dummy.next;
};
 
// 5. Detect cycle — Floyd's tortoise and hare
var hasCycle = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
};

Time: O(n) for every template above Space: O(1) for templates 1 to 5; O(n) for clone-with-map; O(capacity) for design DLL

Common Mistakes#

• Overwriting curr.next before saving the next pointer in reversal — the rest of the list is permanently lost
• Checking fast.next without first checking fast in fast/slow loops (null dereference on odd-length lists)
• Returning dummy instead of dummy.next after building a result list with the dummy head pattern
• Reconnecting odd and even sublists out of order — odd's tail must point at the saved even-head, not at None
• Forgetting that the deepest recursive call in recursive reversal returns the new global head, not the old one

Interview Tips#

• Always start by drawing the list with arrows on the whiteboard or shared doc — pointer questions are unwinnable from pure mental simulation
• State your invariant out loud: "after iteration i, prev points at the new head of the reversed prefix"
• When the problem touches the head node, reach for a dummy head — it eliminates an entire class of edge cases
• If the problem asks for O(1) extra space and the input is sorted or has a "find the middle then reverse" feel, the answer almost certainly combines fast/slow with reversal
• For design problems (LRU, LFU, browser history), bring up sentinel head and tail nodes immediately — interviewers grade harshly when candidates use null checks instead

Follow-up Questions#

• How does the iterative reversal change if the list has a cycle? Hint: detect first, break, then reverse.
• Can you find the middle of an even-length list returning the first middle instead of the second? Hint: check fast.next and fast.next.next instead of fast and fast.next.
• Why does the n-gap technique need n + 1 advances rather than n? Hint: dummy node sits one step before head.
• How do you sort a linked list in O(n log n) time and O(1) extra space? Hint: bottom-up merge sort with width doubling.
• When is a doubly linked list strictly better than two stacks for an LRU implementation? Hint: think about the move-to-front operation.

Key Takeaways#

• Every linked list problem reduces to one of 7 patterns — name the pattern first, then write code
• Iterative reversal with prev / curr / nxt is the single most reused subroutine in the entire track
• Fast/slow pointers solve middle-finding, cycle detection, palindrome checking, and nth-from-end with the same primitive
• Dummy head nodes eliminate the special case for head insertion and deletion across most pointer problems
• Sentinel head and tail in doubly linked lists are what makes O(1) LRU and LFU caches possible
• For O(1) space sorting and O(1) space cloning, look for in-place rewiring tricks (interleaving for clone-with-random)
• Writing 200 lines of templated solutions cold beats writing 20 lines of clever code that fails on a hidden edge case