# Linked Lists — Part 1: The Pattern

A linked list is a chain of nodes where each node points to the next. You lose O(1) indexing, but you gain O(1) insertion and removal **once you hold the neighbouring node**. Interview problems are mostly about **pointer manipulation without losing nodes**, and four techniques cover almost all of them: the **dummy head**, **reversal**, **fast and slow pointers**, and **merging**.

![Reversing a linked list by redirecting one pointer at a time](diagrams/01-reverse-list.svg)

## 1. The Node in Each Language

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

```typescript
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
```


## 2. The Four Techniques

| Technique | Use it for | Key idea |
|---|---|---|
| **Dummy head** | anything that might change the head (removal, merging, insertion) | `dummy = ListNode(0, head)`; return `dummy.next` at the end |
| **Reversal** | reverse a list or a sub-list, palindrome check, reorder | `nxt = cur.next; cur.next = prev; prev = cur; cur = nxt` |
| **Fast & slow** | middle node, cycle detection, k-th from the end | fast moves 2 (or starts k ahead), slow moves 1 |
| **Merge** | merge sorted lists, merge k lists (with a heap) | compare heads, attach the smaller to a tail pointer |

## 3. Templates

```typescript
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
function _build(vals: number[]): ListNode | null {
  const dummy = new ListNode(); let cur = dummy;
  for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
  return dummy.next;
}
function _toList(node: ListNode | null): number[] {
  const out: number[] = [];
  while (node) { out.push(node.val); node = node.next; }
  return out;
}

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) {
    const nxt: ListNode | null = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}
```

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

def _build(vals):
    dummy = cur = ListNode()
    for v in vals:
        cur.next = ListNode(v); cur = cur.next
    return dummy.next

def _to_list(node):
    out = []
    while node:
        out.append(node.val); node = node.next
    return out

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next        # 1. remember the rest
        cur.next = prev       # 2. reverse this pointer
        prev, cur = cur, nxt  # 3. advance both
    return prev

def middle(head):             # fast moves 2, slow moves 1
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow
```

## 4. Floyd's Cycle Detection

If a list has a cycle, a fast pointer (2 steps) and a slow pointer (1 step) must meet inside it: once both are in the cycle, the gap shrinks by one every step. To find **where** the cycle starts, reset one pointer to the head and move both one step at a time; they meet at the cycle entry (the distances work out because `head→entry = meeting point→entry` modulo the cycle length).

## 5. Recognition Cues

- "in place", "O(1) extra space" on a list → pointer manipulation (no copying to an array)
- "middle", "n-th from the end", "cycle" → fast & slow
- "reverse", "palindrome", "reorder L0→Ln→L1→Ln−1" → find middle + reverse second half + merge
- "design an LRU cache" → hash map + doubly linked list

## Under the Hood: Why Interviewers Still Ask About Linked Lists

Real code rarely uses singly linked lists: arrays are faster thanks to CPU cache locality (nodes are scattered in memory, so each hop can be a cache miss). But they test precise reasoning about **mutable references**, and the same pointer patterns appear in LRU caches, allocators (free lists), the Linux kernel's intrusive lists, and the `LinkedHashMap`/`OrderedDict` structures behind real caches.

## Common Pitfalls

1. **Losing the rest of the list:** save `cur.next` before overwriting it.
2. **Special-casing the head** instead of using a dummy node.
3. **Null dereference:** check `fast and fast.next` before `fast.next.next`.
4. **Off-by-one for "n-th from the end":** move `fast` n steps ahead of `slow`, starting both at the dummy.
5. **Creating cycles accidentally** when reordering (terminate the first half with `None`).

## Quick Reference

```text
dummy = ListNode(0, head) … return dummy.next
reverse: nxt=cur.next; cur.next=prev; prev=cur; cur=nxt
middle: slow, fast = head, head; while fast and fast.next: slow=slow.next; fast=fast.next.next
cycle: meet → reset one to head → step both → entry
O(n) time · O(1) extra space for all of the above
```