Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Linked Lists

Linked list problems test precise pointer manipulation. Master four techniques (dummy head, reversal, fast and slow pointers, merging), understand Floyd's cycle detection, and watch reversal, cycle detection and remove-nth-from-end animated before tackling LRU Cache.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 13 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

The node type in Python, TypeScript and C#
Dummy head, reversal, fast/slow pointers and merging
Floyd's cycle detection and finding the entry
Six LeetCode problems up to LRU Cache

📚 Before you start

Part 1The 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

1The 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;
  }
}

2The 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

3Templates

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

4Floyd'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).

5Recognition 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 HoodWhy 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

Losing the rest of the list: save cur.next before overwriting it.
Special-casing the head instead of using a dummy node.
Null dereference: check fast and fast.next before fast.next.next.
Off-by-one for "n-th from the end": move fast n steps ahead of slow, starting both at the dummy.
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

Part 2Interview Problems

Six problems combining the four techniques, ending with LRU Cache, one of the most frequently asked design questions.

1Reverse Linked List (LeetCode 206)

🟢 Easy. Reverse a singly linked list and return the new head.

text

1 → 2 → 3 → 4 → 5  ⇒  5 → 4 → 3 → 2 → 1

Approach. Iterate with prev and cur; at each node save next, point cur.next back to prev, advance. (Recursive version: reverse the rest, then head.next.next = head; head.next = None, O(n) stack.)

Complexity. O(n) time, O(1) space.

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, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

2Merge Two Sorted Lists (LeetCode 21)

🟢 Easy. Merge two sorted linked lists into one sorted list by splicing their nodes.

text

1→2→4 and 1→3→4 ⇒ 1→1→2→3→4→4

Approach. Dummy head + tail pointer: repeatedly attach the smaller head, advance it; at the end attach whatever remains.

Complexity. O(n + m) time, O(1) space.

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 mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(); let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

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 merge_two_lists(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

3Linked List Cycle (LeetCode 141)

🟢 Easy. Return true if the linked list contains a cycle.

text

3 → 2 → 0 → -4 → (back to 2) → true

Approach. Floyd's tortoise and hare: slow moves 1, fast moves 2. If fast reaches the end there's no cycle; if they meet, there is.

Complexity. O(n) time, O(1) space (a visited set also works in O(n) space).

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 hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

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 has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

4Remove Nth Node From End of List (LeetCode 19)

🟠 Medium. Remove the n-th node from the end of the list in one pass and return the head.

text

1→2→3→4→5, n = 2 ⇒ 1→2→3→5

Approach. Dummy head; move fast n steps ahead of slow; then move both until fast.next is null. Now slow.next is the node to delete. The dummy handles removing the head itself.

Complexity. O(L) time, O(1) space.

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 removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let slow: ListNode = dummy, fast: ListNode = dummy;
  for (let i = 0; i < n; i++) fast = fast.next!;
  while (fast.next) { slow = slow.next!; fast = fast.next; }
  slow.next = slow.next!.next;
  return dummy.next;
}

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 remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

5Reorder List (LeetCode 143)

🟠 Medium. Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … in place.

text

1→2→3→4→5 ⇒ 1→5→2→4→3

Approach. Three techniques in sequence: find the middle (fast/slow), reverse the second half, then merge the two halves alternately. Cut the first half with slow.next = None to avoid a cycle.

Complexity. O(n) time, O(1) space.

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 reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;
  let slow: ListNode = head, fast: ListNode = head;
  while (fast.next && fast.next.next) { slow = slow.next!; fast = fast.next.next; }
  let second: ListNode | null = slow.next; slow.next = null;
  let prev: ListNode | null = null;
  while (second) { const nxt: ListNode | null = second.next; second.next = prev; prev = second; second = nxt; }
  let first: ListNode | null = head; second = prev;
  while (second) {
    const n1: ListNode | null = first!.next, n2: ListNode | null = second.next;
    first!.next = second; second.next = n1;
    first = n1; second = n2;
  }
}

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 reorder_list(head):
    if not head or not head.next:
        return
    slow = fast = head
    while fast.next and fast.next.next:          # 1. middle
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None
    prev = None
    while second:                                 # 2. reverse second half
        second.next, prev, second = prev, second, second.next
    first, second = head, prev
    while second:                                 # 3. merge alternately
        n1, n2 = first.next, second.next
        first.next, second.next = second, n1
        first, second = n1, n2

6LRU Cache (LeetCode 146)

🟠 Medium. Design a cache with capacity c: get(key) returns the value or −1; put(key, value) inserts/updates and evicts the least recently used key when over capacity. Both in O(1).

text

cap 2: put(1,1) put(2,2) get(1)→1 put(3,3) [evicts 2] get(2)→-1 put(4,4) [evicts 1] get(1)→-1

Approach. A hash map from key to node gives O(1) lookup; a doubly linked list ordered by recency gives O(1) move-to-front and evict-from-back. Python's OrderedDict and JavaScript's insertion-ordered Map implement exactly this pair, so in interviews say what they do internally (and be ready to write the linked list by hand).

Complexity. O(1) per operation, O(capacity) space.

typescript

class LRUCache {
  private map = new Map<number, number>();     // Map keeps insertion order: first key = least recent
  private capacity: number;
  constructor(capacity: number) { this.capacity = capacity; }
  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key)!;
    this.map.delete(key);
    this.map.set(key, v);                      // move to most-recent end
    return v;
  }
  put(key: number, value: number): void {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) this.map.delete(this.map.keys().next().value!);
  }
}

python

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()          # sentinels: head.next = most recent
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

🧠 Key takeaways

Four techniques: dummy head, reversal, fast & slow, merge.
Save cur.next before overwriting it; a dummy node removes head special cases.
Floyd: pointers meet inside a cycle; reset one to the head to find the entry.
LRU Cache = hash map + doubly linked list (OrderedDict / ordered Map internally).

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_linked_lists_exercise_1.py

TS PY

algo_linked_lists_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Why use a dummy head?

Uniform code.

2. Fast moves 2, slow moves 1. When fast reaches the end, slow is…

Half the distance.

3. Which structures make LRU Cache O(1)?

Lookup + reorder.

4. Reorder List combines which steps?

Three techniques.

Source: algo_linked_lists_theory_1.md, algo_linked_lists_theory_2.md · generated by tools/build_lessons.py