Linked List Pattern

The Linked List pattern utilizes sequential node references (pointers) to traverse and edit linear node sequences, enabling constant-time node insertions and deletions at any active pointer position without resizing arrays.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The input data structure is explicitly defined as a singly or doubly linked list.
• You need to perform frequent insertions or deletions at the start, end, or middle of a list in O(1) time.
• The task requires reversing a list in-place, finding the middle node, or detecting if a loop/cycle exists.

How It Works

Instead of storing elements in contiguous memory (like arrays), linked lists connect nodes using pointers (next and optionally prev).

• To reverse a list, you iterate through the nodes, shifting pointer references: point each node’s next pointer to its predecessor instead of its successor.
• To detect cycles, you use Fast & Slow pointers (Floyd’s algorithm): the slow pointer moves 1 node per step, the fast pointer moves 2 nodes. If they meet, a cycle exists.

For example, to reverse 1 -> 2 -> 3:

1. Track three pointers: prev = null, curr = 1, nxt = null.
2. Save successor: nxt = curr.next (2).
3. Reverse link: curr.next = prev (null).
4. Shift states: prev = curr (1), curr = nxt (2).
5. Repeat for subsequent nodes.

Complexity, With Caveats

• Time Complexity: O(1) for node insertions and deletions if you already hold a reference to the insertion point. O(n) to traverse to a specific index or value, as you must step through nodes sequentially.
• Space Complexity: O(1) auxiliary space when modifying pointers in-place. If you allocate cloned nodes recursively, space increases to O(n).

Minimal Code Template

public class LinkedListTemplate {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    // In-Place Reversal
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next; // save successor
            curr.next = prev;              // reverse pointer
            prev = curr;                   // shift prev
            curr = nextTemp;               // shift curr
        }
        return prev; // new head of the reversed list
    }
}

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# In-Place Reversal
def reverse(head: ListNode) -> ListNode:
    prev = None
    curr = head

    while curr:
        next_temp = curr.next  # save successor
        curr.next = prev  # reverse pointer
        prev = curr  # shift prev
        curr = next_temp  # shift curr

    return prev  # new head of the reversed list

class LinkedListTemplate {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {}
    };

    // In-Place Reversal
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* nextTemp = curr->next; // save successor
            curr->next = prev;              // reverse pointer
            prev = curr;                   // shift prev
            curr = nextTemp;               // shift curr
        }
        return prev; // new head of the reversed list
    }
};

Where This Pattern Falls Short

• Random access: Linked lists do not support index-based random access. Finding list[i] takes O(i) steps, whereas arrays support O(1) offset access.
• Cache locality: Nodes are allocated dynamically in heap memory and can be scattered across different memory locations, resulting in poor CPU cache locality compared to contiguous arrays.

Related Patterns, Compared

• Two Pointers: choose this specialized sub-pattern (Fast & Slow pointers) to detect cycles or locate the middle node of a linked list in a single pass without extra memory.
• Dummy Node: choose this helper pattern when you need to handle boundary changes (like inserting at the head of the list or merging lists) to avoid special-casing null values.

Frequently Asked Questions

Why do we use a dummy node? A dummy node (dummy = ListNode(0)) acts as a placeholder before the head of the list. It simplifies operations that modify the head, allowing you to return dummy.next without checking if the head is null.

How does Floyd’s cycle detection algorithm work? By using a slow pointer and a fast pointer. If there is a loop, the fast pointer will enter the loop first and eventually “lap” the slow pointer from behind, meeting at some node. If there is no loop, the fast pointer will reach null.

What does this pattern test in interviews? It tests your comfort with pointer manipulation, memory allocation, and handling edge cases like empty lists or loops.