# Linked Lists — Part 2: Interview Problems

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

## 1. Reverse 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
```

## 2. Merge 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
```

## 3. Linked 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
```

## 4. Remove 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
```

## 5. Reorder 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
```

## 6. LRU 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]
```