Linked Lists

A linked list is a chain of nodes, where each node stores a value and a reference ("pointer") to the next node in the chain. Unlike an array, the elements are not stored contiguously in memory, so there is no random access by index — you can only reach a node by walking the chain from the head, one next pointer at a time. A singly linked list has one link per node (next), pointing forward only. A doubly linked list adds a prev link, so you can walk backward too, at the cost of extra memory per node. That backward link is exactly what makes structures like an LRU cache efficient: you can splice a node out of the middle of the list in O(1) time without rescanning from the head.

The mental model that unlocks almost every linked-list problem is simple: at each step you are holding onto a small, fixed number of node references (usually named prev, curr, and next), and you rewire the arrows between them before moving forward. The danger is that once you overwrite a node's next pointer, you lose the only way to reach whatever used to follow it — so the golden rule is: save the pointer to what comes next before you overwrite anything. A generic rewiring loop looks like this:

prev = None
curr = head
while curr is not None:
    next_node = curr.next   # save it first
    curr.next = prev        # rewire
    prev = curr             # advance
    curr = next_node

This is the heart of in-place reversal, and it generalizes: many linked-list problems (removing a node, reordering a list, detecting a cycle, merging two lists) are variations on "walk with one or two pointers, capture what you need before you overwrite it, and reconnect." Doing this in place is valuable because it uses O(1) extra space — you never need to clone the list into an array or a new set of nodes, you just rearrange the existing links.

A second recurring idiom is the dummy head (or sentinel) node: a throwaway node placed before the real head, whose next points at the actual list. It removes the need for special-case code when the head itself might change (e.g., deleting the first node), because you can always operate on dummy.next uniformly. A third idiom is the two-pointer / runner technique: advancing one pointer faster than another (or starting one pointer k steps ahead) lets you find the middle, detect a cycle, or find the k-th-from-last node in a single pass without knowing the list's length in advance.

Complexity characteristics: traversal, reversal, and most single-pass rewiring operations run in O(n) time and O(1) extra space, since you visit each node once and only ever hold a constant number of references. Recursive formulations of the same operations are O(n) time but O(n) space due to the call stack, so iterative solutions are usually preferred in interviews unless recursion clarifies the logic.

Common pitfalls: overwriting curr.next before saving it (permanently losing the rest of the list), off-by-one errors when computing "k-th from the end" (should the count include the target node itself?), forgetting to handle the empty list (head is None) or single-node list as base cases, forgetting to null out a node's stray next/child pointer when splicing it elsewhere (which can silently create a cycle), and mixing up whether you're comparing node identity versus node value.

This subject walks through six problems that build on these ideas: Linked List Reversal (the fundamental rewiring loop), Remove the Kth Last Node From a Linked List (two-pointer offset technique), Linked List Intersection (pointer-swapping trick to align two lists), LRU Cache (doubly linked list + hash map for O(1) operations), Palindromic Linked List (find the middle, reverse the second half, compare), and Flatten a Multi-Level Linked List (depth-first pointer rewiring with a child pointer). By the end, you should be comfortable reasoning about pointers on paper before writing a line of code.