Linked Lists

A linked list trades random access for cheap insertion. You cannot jump to index k — you must follow k pointers — but splicing a node in or out is O(1) once you are holding the right reference. Every technique below exists because of that trade.

The Three Techniques

1. Careful pointer rewiring

The defining hazard: overwriting a next pointer destroys your only reference to the rest of the list. Always save before you overwrite.

• Reverse Linked List — the canonical three-pointer dance

2. Fast and slow pointers

Two pointers moving at different rates turn several questions into a single pass.

• Middle of the Linked List — one step versus two
• Linked List Cycle II — Floyd's algorithm, with a distance proof

3. The dummy head

Create a throwaway node in front of the result. Every append becomes uniform, and the "what about the first node?" special case disappears.

• Merge Two Sorted Lists — the clearest demonstration

Node Definitions

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

Identity vs. Value

A recurring source of wrong answers: two nodes holding the same number are not the same node. When a problem asks where two lists intersect, or whether a list revisits a node, compare with is in Python and === in TypeScript — never .val.

• Intersection of Two Linked Lists — built entirely around this distinction

All Problems