Advanced Linked List Patterns: Deep Copy and LRU Cache

Linked lists at the basic level — reverse, cycle detection, merging — are well-covered territory. But two problems consistently show up in mid-to-senior interviews that require you to think differently about linked list manipulation: deep-copying a list with random pointers, and implementing an LRU cache.

Both problems look harder than they are once you see the underlying pattern. The deep copy is about managing identity (which clone corresponds to which original). The LRU cache is about building a data structure with O(1) access and O(1) eviction — which turns out to require a specific combination of two structures you already know.

Problem 1: Copy List with Random Pointer (LeetCode 138)

Each node in this list has a next pointer (standard) and a random pointer that can point to any node in the list, or null. Build a complete deep copy — every node in the new list should be new, and both next and random should point to the correct copies.

The tricky part: when you're creating the copy of node A, the random pointer might point to node C, which you haven't created yet. So you can't just copy in a single pass naively.

Brute Force: Two-Pass with HashMap

Pass 1: Create all the clone nodes and map each original to its clone. Don't wire up pointers yet.

Pass 2: Use the map to connect next and random on the clones.

// Time: O(n)  Space: O(n)
const copyRandomList = (head) => {
  if (!head) return null;
 
  // Pass 1: create all clone nodes
  const map = new Map(); // original node → clone node
  let curr = head;
  while (curr) {
    map.set(curr, { val: curr.val, next: null, random: null });
    curr = curr.next;
  }
 
  // Pass 2: wire up next and random pointers
  curr = head;
  while (curr) {
    const clone = map.get(curr);
    clone.next = curr.next ? map.get(curr.next) : null;
    clone.random = curr.random ? map.get(curr.random) : null;
    curr = curr.next;
  }
 
  return map.get(head);
};

This is clean, readable, and O(n) time. The O(n) space comes from the HashMap. Most interviewers are happy with this — it's the right approach.

But there's a follow-up coming: "Can you do it in O(1) space?"

Optimized: Interleaved Clone Nodes

Here's the O(1) space trick. Instead of a HashMap to track which clone corresponds to which original, you physically interleave the clones into the original list.

After pass 1:

original: A → B → C → null
becomes:  A → A' → B → B' → C → C' → null

Each clone node sits immediately after its original. So the clone of any node X is just X.next.

Pass 2: set random on each clone. X.random should point to the clone of X.original.random, which is X.original.random.next.

Pass 3: separate the two lists.

// Time: O(n)  Space: O(1)
const copyRandomListO1 = (head) => {
  if (!head) return null;
 
  // Pass 1: interleave clones
  // A → A' → B → B' → C → C'
  let curr = head;
  while (curr) {
    const clone = { val: curr.val, next: curr.next, random: null };
    curr.next = clone;
    curr = clone.next; // advance to original B
  }
 
  // Pass 2: set random on clones
  // clone of X is X.next, so X.random's clone is X.random.next
  curr = head;
  while (curr) {
    const clone = curr.next;
    clone.random = curr.random ? curr.random.next : null;
    curr = clone.next; // advance to original B
  }
 
  // Pass 3: separate the two lists
  const cloneHead = head.next;
  curr = head;
  while (curr) {
    const clone = curr.next;
    curr.next = clone.next;          // restore original list
    clone.next = clone.next ? clone.next.next : null; // wire clone list
    curr = curr.next;
  }
 
  return cloneHead;
};

Walk through with A → B → C, where A.random = C, B.random = A, C.random = null:

Problem 2: LRU Cache (LeetCode 146)

Design a data structure that supports:

• get(key): return value if it exists, -1 otherwise. Mark key as most-recently-used.
• put(key, value): insert or update. If at capacity, evict the least-recently-used key.

Both operations must run in O(1).

Why You Need Two Data Structures

A HashMap alone gives you O(1) lookup, but no ordering. You can't find the LRU item quickly.

An array or list gives you ordering, but lookup is O(n).

You need both. The standard implementation: HashMap + doubly linked list.

The doubly linked list maintains access order: most-recently-used at the head (or tail, your choice), least-recently-used at the other end. The HashMap maps each key to its node in the linked list.

When you access a key: find it in O(1) via the HashMap, then move its node to the front/back of the list (O(1) with a doubly linked list — just rewire 4 pointers).

When you evict: remove from the tail/head of the list (O(1)) and delete from the HashMap.

Using two dummy sentinel nodes (head and tail) eliminates null-checks when inserting/removing at the boundaries. This is a common trick worth knowing.

// Time: O(1) for both get and put  Space: O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key → node
 
    // Dummy sentinels so we never null-check boundaries
    this.head = { key: 0, val: 0, prev: null, next: null }; // MRU side
    this.tail = { key: 0, val: 0, prev: null, next: null }; // LRU side
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  // Remove a node from its current position in the list
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
 
  // Insert a node right after head (most-recently-used position)
  _insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
 
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    // Move to MRU position
    this._remove(node);
    this._insertFront(node);
    return node.val;
  }
 
  put(key, value) {
    if (this.map.has(key)) {
      // Update existing — move to front
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._insertFront(node);
    } else {
      // Insert new
      if (this.map.size === this.capacity) {
        // Evict LRU: the node just before tail
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
      const node = { key, val: value, prev: null, next: null };
      this._insertFront(node);
      this.map.set(key, node);
    }
  }
}

Walk through capacity = 2, operations put(1,1), put(2,2), get(1), put(3,3), get(2):

2 was the LRU when we inserted 3, so it got evicted. get(2) returns -1.

JavaScript Map Shortcut

JavaScript's Map preserves insertion order. You can abuse this to implement a simpler LRU without a manual doubly linked list:

// Time: O(1) amortized  Space: O(capacity)
// (delete + re-insert to refresh order)
class LRUCacheMap {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
 
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    // Refresh: delete and re-insert to put at end (most recent)
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }
 
  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size === this.capacity) {
      // .keys().next().value gives the first (oldest) key
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

This works and is much shorter. The caveat: it relies on Map's iteration order guarantee (insertion order), which is spec-compliant in JS but not universal across languages. In an interview, mention that you know about this shortcut but want to show the "real" implementation with a doubly linked list first.

Interview Tips

For Copy List with Random Pointer:

Start with the HashMap approach. It's clean and correct. If they ask about O(1) space, explain the interleaving technique verbally before coding — draw it out: "I'm going to insert each clone node directly after its original, so clone of X is always at X.next." Interviewers follow this much better with a diagram.

The pass 2 random assignment is the tricky part: clone.random = curr.random?.next. Walk through this with a concrete example when explaining.

For LRU Cache:

This is a design problem as much as a coding problem. Before writing code, say: "I need O(1) lookup and O(1) order tracking. That's HashMap plus doubly linked list." Sketch the structure. The sentinel nodes are a nice touch — explain them: "Dummy head and tail let me do insert/remove without null-checking the boundaries."

The _remove and _insertFront helpers make the main logic cleaner. Factoring these out is worth mentioning.

Common mistakes to avoid:

• Forgetting to update the HashMap when evicting (memory leak in spirit)
• Mixing up which end is MRU vs LRU — be consistent and state it explicitly
• Missing the update case in put (key already exists, don't insert a duplicate node)

The capacity check in put: Check this.map.size === this.capacity before inserting, not after. You want to evict first, then insert.

Both problems test whether you can juggle multiple data structures at once while keeping all invariants synchronized. The code isn't complicated — the challenge is staying organized under pressure.