Linked Lists

Linked Lists represent a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and the previous node.

1. Structure: Singly vs. Doubly

Unlike arrays, linked lists do not have a fixed size and are not stored contiguously in memory.

2. The "Runner" Technique (Fast & Slow Pointers)

This is a powerful technique for solving cycle detection and finding the middle of a list. You iterate through the list with two pointers at different speeds:

• Slow Pointer: Moves 1 step at a time.
• Fast Pointer: Moves 2 steps at a time.

Common Applications:

• Cycle Detection: If the fast pointer catches up to the slow pointer, there is a cycle.
• Middle Element: When the fast pointer reaches the end, the slow pointer will be at the middle.

3. Reusable Techniques

These patterns show up across many linked list problems and help reduce edge cases.

• Dummy Nodes: Use a placeholder head to simplify insertions and merges when the real head can change.
• Reversal Problems: Master pointer rewiring to reverse a whole list or a sublist in-place.
• Slow and Fast Pointers: Use different speeds to detect cycles, find midpoints, or split lists.

4. Recursive Problems

Many linked list problems can be solved recursively, often with cleaner code than the iterative approach (though watch out for stack overflow on long lists).

Example: Recursive Reverse

def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head