Linked lists

A linked list is useful when identity and rewiring matter more than indexed access. Most bugs come from overwriting the only pointer to unread nodes.

Draw roles, not variable names

flowchart LR
  accTitle: Reversing one linked-list edge safely
  accDescr: The previous pointer owns the reversed prefix, current is the node being moved, and following preserves access to the unread suffix before current next is reversed.
  P["previous<br/>reversed prefix"] <-- C["current"]
  C -. "save first" .-> N["following<br/>unread suffix"]

At the start of every iteration:

• previous heads a correctly reversed prefix;
• current heads the untouched suffix;
• the two regions contain every original node exactly once.

Iterative reversal

PythonC++17C++11

@dataclass
class ListNode:
    value: int
    next: ListNode | None = None


def reverse_linked_list(head: ListNode | None) -> ListNode | None:
    """Reverse a singly linked list in place and return its new head."""
    previous: ListNode | None = None
    current = head
    while current is not None:
        # Save the unread suffix before changing the only forward link.
        following = current.next
        current.next = previous
        # Advance both boundaries of the reversed prefix.
        previous, current = current, following
    return previous

struct ListNode {
  explicit ListNode(int node_value, ListNode* next_node = nullptr)
      : value(node_value), next(next_node) {}

  int value;
  ListNode* next;
};

inline ListNode* reverse_linked_list(ListNode* head) {
  ListNode* previous = nullptr;
  ListNode* current = head;
  while (current != nullptr) {
    // Save the unread suffix before changing the only forward link.
    ListNode* following = current->next;
    current->next = previous;
    // Advance both boundaries of the reversed prefix.
    previous = current;
    current = following;
  }
  return previous;
}

struct ListNode {
  explicit ListNode(int node_value, ListNode* next_node = nullptr)
      : value(node_value), next(next_node) {}

  int value;
  ListNode* next;
};

inline ListNode* reverse_linked_list(ListNode* head) {
  ListNode* previous = nullptr;
  ListNode* current = head;
  while (current != nullptr) {
    // Save the unread suffix before changing the only forward link.
    ListNode* following = current->next;
    current->next = previous;
    // Advance both boundaries of the reversed prefix.
    previous = current;
    current = following;
  }
  return previous;
}

Time is O(n) and auxiliary space is O(1). Prefer iteration when recursion would add one call frame per node.

Pattern chooser

Signal	Pattern	Proof checkpoint
Delete/insert near the head	Dummy sentinel	The answer head is always dummy.next
Middle, cycle, or k-from-end	Slow/fast pointers	State the distance between pointers
Merge sorted lists	Tail builder	Tail always ends the merged prefix
Reverse a segment	Save four boundaries	Reconnect prefix, segment, and suffix
Cache with recency	List + hash map	Map and list own exactly the same live keys

Failure checks

• Save next before rewriting it.
• Decide whether the function may mutate the input.
• Test empty, one-node, two-node, and cyclic inputs separately.
• In C++, make node ownership explicit; this template rewires non-owning raw pointers and does not allocate or delete nodes.

Practice ladder

1. Reverse Linked List — one invariant.
2. Merge Two Sorted Lists — dummy sentinel.
3. Linked List Cycle II — prove the meeting geometry.
4. Reverse Nodes in k-Group — preserve group boundaries.