The Frontend Engineer's LeetCode Blueprint, Part 2: The Pointer & Memory Playground

Part 2: The Pointer & Memory Playground (Linked Lists, Monotonic Stacks, and In-Memory System Design)

The Frontend Paradox: "We Don't Use Linked Lists"

Ask any frontend engineer when they last used a linked list in production, and they’ll probably say: "Never. We have Array.prototype.map and immutable state."

And they’d be wrong.

• The DOM Tree is connected via pointer references: node.nextSibling, node.previousSibling, and node.parentNode.
• React Fiber—the reconciler architecture powering React 16 through 19—is literally an in-memory singly linked list tree of fiber nodes with child, sibling, and return pointers.
• The Browser History Stack and Undo/Redo buffers in rich text editors are built on doubly linked lists.

When Toptal, Meta, or Stripe throw linked list and stack problems at a senior frontend candidate, they aren't testing whether you can build a todo app. They are testing pointer discipline, reference safety, and your ability to reason about mutating heap objects without triggering an infamous:

TypeError: Cannot read properties of null (reading 'next')

In this article, we’re going to master pointer manipulation, uncover the "cheat code" data structure known as the Monotonic Stack, and build an industrial-strength LRU Cache from scratch without relying on language-level shortcuts.

1. The Anatomy of a JS Linked List & The "Dummy Head" Superweapon

In languages like C++, nodes sit in contiguous blocks or explicit heap allocations with manual memory management. In JavaScript:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next; // Just a reference to another object on the V8 heap
  }
}

Because variables in JavaScript hold references to objects, copying a node does not duplicate the node—it creates another pointer pointing to the exact same memory address.

The Number One Bug in Interview Code

Consider this common disaster:

// You want to modify the list, but you lose the original head:
function badOperation(head) {
  head = head.next; // The original head is now disconnected or lost from your return path!
  return head;
}

The Universal Cure: The Sentinel (Dummy) Node

Whenever you need to:

1. Delete the first node of a list
2. Insert before the head
3. Merge or reorganize lists where the new head is uncertain

Always create a dummy node.

const dummy = new ListNode(-1);
dummy.next = head;
let current = dummy;

By returning dummy.next at the end of the function, you eliminate 90% of if (head === null) or if (current === head) branch conditions.

2. Fast & Slow Pointers (Floyd’s Cycle Algorithm)

The "Tortoise and Hare" algorithm relies on two pointers moving at different speeds across references.

Slow (1 step):  (A) -> (B) -> (C) -> (D)
Fast (2 steps): (A) --------> (C) --------> (E)

Key Use Cases:

1. Finding the midpoint of a list in one pass: When fast reaches the end (null), slow is guaranteed to be at the center.
2. Detecting cycles: If there is a loop, fast will eventually lap slow inside the cycle.

Challenge 1: Reverse Nodes in k-Group (LeetCode 25 - Hard)

Let's bypass easy problems and tackle one of the most notoriously failed linked list problems on LeetCode.

Problem: Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer less than or equal to the length of the linked list. If the number of nodes is not a multiple of k, then left-out nodes at the end should remain as they are. You must use only O(1) extra memory.

Input:  [1] -> [2] -> [3] -> [4] -> [5],  k = 3
Output: [3] -> [2] -> [1] -> [4] -> [5]

Why People Fail This:

They try to swap node values. Swapping values in an interview will get you disqualified instantly—interviewers want to see you rewire the pointers.

The Blueprint:

1. Create a dummy node pointing to head.
2. Find the k-th node from the current group anchor. If fewer than k nodes remain, stop.
3. Disconnect the k-group, reverse it in-place using standard 3-pointer reversal (prev, curr, nextTemp).
4. Re-stitch the reversed segment back to the preceding group and the next remaining segment.
5. Move the anchor forward and repeat.

Before reversal (k = 2):
groupPrev -> [1] -> [2] -> [3] -> ...
              ^      ^
            curr    kth

After reversing [1] -> [2]:
groupPrev -> [2] -> [1] -> [3] -> ...
                     ^
                 groupPrev moves here for the next group!

The Production Code:

/**
 * Time Complexity:  O(n) - Each node is traversed and reversed exactly once
 * Space Complexity: O(1) - Constant pointer mutations
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
function reverseKGroup(head, k) {
  if (!head || k <= 1) return head;

  const dummy = new ListNode(0);
  dummy.next = head;

  let groupPrev = dummy;

  while (true) {
    // 1. Verify if k nodes exist in the current group
    const kth = getKthNode(groupPrev, k);
    if (!kth) break;

    const groupNext = kth.next;

    // 2. Reverse the k nodes between groupPrev and groupNext
    let prev = groupNext;
    let curr = groupPrev.next;

    while (curr !== groupNext) {
      const tempNext = curr.next;
      curr.next = prev;
      prev = curr;
      curr = tempNext;
    }

    // 3. Rewire the connection from the previous group
    const nextGroupPrev = groupPrev.next; // [1] is now the tail of this reversed segment
    groupPrev.next = kth;                 // groupPrev now points to [2] (the new head)
    groupPrev = nextGroupPrev;            // move groupPrev to [1]
  }

  return dummy.next;
}

/**
 * Helper to advance k steps forward
 */
function getKthNode(curr, k) {
  while (curr && k > 0) {
    curr = curr.next;
    k--;
  }
  return curr;
}

3. The Monotonic Stack: The Ultimate Cheat Code

If a problem asks for:

• "The next greater element for every index"
• "The nearest smaller element on the left"
• "The maximum area bounded by adjacent elements"

Stop thinking about nested loops. You are looking at a Monotonic Stack.

What is It?

A stack that preserves a strictly increasing or decreasing order of values. As you iterate through an array:

• If the current element violates the monotonic property, you pop elements off the stack until the order is restored.
• Each popped element has just met its "destiny"—the current element is the first element that is larger (or smaller) than it!

Challenge 2: Largest Rectangle in Histogram (LeetCode 84 - Hard)

Problem: Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Heights: [2, 1, 5, 6, 2, 3]

         [6]
      [5][#]
      [#][#]   [3]
[2]   [#][#][2][#]
[#][1][#][#][#][#]
-------------------
Max rectangle is formed by heights 5 and 6:
Width = 2, Height = 5 -> Area = 10

The Brute-Force Trap:

For every bar i, extend outward to the left and right until hitting a bar shorter than heights[i]. Calculate width * heights[i]. This takes O(n^2) time and triggers an instant Time Limit Exceeded.

The Monotonic Stack Intuition:

We want to find:

1. The first index to the left that is shorter than heights[i].
2. The first index to the right that is shorter than heights[i].

If we keep a stack of indices with monotonically increasing heights:

• When we see a bar curr that is shorter than the bar at stack.peek(), that means the bar at stack.peek() cannot extend any further to the right!
• We pop the bar from the stack: this is our h (height).
• The right boundary is i.
• The left boundary is the new stack.peek() (the nearest shorter bar to its left).
• Width = i - stack.peek() - 1.
• Area = h × width.

The Code (with Sentinel Values):

/**
 * Time Complexity:  O(n) - Each index is pushed and popped exactly once
 * Space Complexity: O(n) - Stack stores indices
 * @param {number[]} heights
 * @return {number}
 */
function largestRectangleArea(heights) {
  if (!heights || heights.length === 0) return 0;

  // Append a 0 at the end as a dummy sentinel.
  // This guarantees that all remaining elements in the stack will be popped out at the end!
  const extendedHeights = [...heights, 0];
  const stack = []; // Stores indices
  let maxArea = 0;

  for (let i = 0; i < extendedHeights.length; i++) {
    const currentHeight = extendedHeights[i];

    // Maintain a strictly increasing stack
    while (stack.length > 0 && extendedHeights[stack[stack.length - 1]] > currentHeight) {
      const poppedIndex = stack.pop();
      const height = extendedHeights[poppedIndex];

      // If stack is empty, it means 'height' was the smallest seen so far; width extends to index 0
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;

      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}

Look at how concise that is. A problem that terrorizes 80% of candidates collapses into 15 lines of JavaScript once you wield the monotonic stack.

4. In-Memory System Design: The LRU Cache (LeetCode 146)

In frontend architecture, LRU (Least Recently Used) caching is everywhere:

• Caching computed selectors (Reselect/Memoize).
• Image caching in canvas / WebGL texture renderers.
• Storing paginated API results in Apollo Client or React Query.

Problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

• get(key): Return the value if the key exists, otherwise return -1. O(1) time.
• put(key, value): Update or insert the value. If keys exceed capacity, evict the least recently used key. O(1) time.

The JavaScript Cheat (And Why Interviewers Reject It)

In JavaScript, standard Map objects remember the original insertion order of keys:

// The "cheater" interview trick:
const map = new Map();
map.set('a', 1);
map.delete('a');
map.set('a', 1); // Moves 'a' to the most recent insertion position!

If you write this in a senior interview at Toptal, the interviewer will say:

"Great. You know the ECMAScript specification for Map iteration order. Now build it without using Map's internal linked hash map mechanics."

The True Engineering Solution: Doubly Linked List + Hash Map

To achieve guaranteed O(1) operations:

1. Hash Map (Map): Maps key → DListNode reference (O(1) lookup).
2. Doubly Linked List (DListNode):
   • Head sentinel: Represents Most Recently Used (MRU).
   • Tail sentinel: Represents Least Recently Used (LRU).
   • Node removal: O(1) because each node has .prev and .next. No array shifts!

[HEAD] <-> [Node A (MRU)] <-> [Node B] <-> [Node C (LRU)] <-> [TAIL]
  |               ^
  |_______________| (New or updated nodes inserted directly behind HEAD)

The Industrial-Grade Implementation:

class DListNode {
  constructor(key = 0, val = 0) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  /**
   * @param {number} capacity
   */
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // key -> DListNode

    // Sentinel dummy nodes to avoid edge-case pointer checks
    this.head = new DListNode();
    this.tail = new DListNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * @param {number} key
   * @return {number}
   */
  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }

    const node = this.cache.get(key);
    // Accessed node becomes most recently used: move to head
    this._moveToHead(node);
    return node.val;
  }

  /**
   * @param {number} key
   * @param {number} value
   * @return {void}
   */
  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.val = value;
      this._moveToHead(node);
    } else {
      const newNode = new DListNode(key, value);
      this.cache.set(key, newNode);
      this._addNode(newNode);

      if (this.cache.size > this.capacity) {
        // Evict the least recently used node (before tail)
        const lru = this._popTail();
        this.cache.delete(lru.key);
      }
    }
  }

  // --- Internal Pointer Helpers ---

  /**
   * Always insert new node right after dummy head
   */
  _addNode(node) {
    node.prev = this.head;
    node.next = this.head.next;

    this.head.next.prev = node;
    this.head.next = node;
  }

  /**
   * Unlink an existing node from the list
   */
  _removeNode(node) {
    const prevNode = node.prev;
    const nextNode = node.next;

    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }

  /**
   * Move an existing node to head (mark as most recently used)
   */
  _moveToHead(node) {
    this._removeNode(node);
    this._addNode(node);
  }

  /**
   * Remove and return the node immediately before dummy tail
   */
  _popTail() {
    const lruNode = this.tail.prev;
    this._removeNode(lruNode);
    return lruNode;
  }
}

Notice how clean the code becomes when using this.head and this.tail sentinels. No if (this.size === 1) or if (!this.head) checks anywhere!

5. Memory Management & V8 Traps in Linked Lists

When writing linked structures in long-running Node.js or browser environments:

The Dangling Pointer Memory Leak

In JavaScript, garbage collection (GC) uses Mark-and-Sweep. If you detach a node from your linked list:

node.prev.next = node.next;
node.next.prev = node.prev;

If that node is still referenced in a closure, global variable, or a cache map, the entire linked list connected to it will not be collected!

Always sever references when discarding nodes:

node.prev = null;
node.next = null;

6. The Part 2 Practice Gauntlet

Before proceeding to Part 3, build muscle memory by solving these:

1. LeetCode 141 (Easy) & 142 (Medium): Linked List Cycle I & II (Floyd's algorithm basics).
2. LeetCode 143 (Medium): Reorder List (Combines finding midpoint, reversing second half, and merging lists).
3. LeetCode 739 (Medium): Daily Temperatures (Your gateway monotonic stack drill).
4. LeetCode 84 (Hard): Largest Rectangle in Histogram (Implement without looking at this guide).
5. LeetCode 146 (Medium): LRU Cache (Write the Doubly Linked List version from scratch in an empty editor).

What’s Coming Next in Part 3

Now that we have conquered linear data structures, pointers, and custom in-memory systems, we enter the world of non-linear algorithms:

• Trees & Graphs through the Frontend Lens: Turning the Virtual DOM and dependency graphs into algorithmic graphs.
• Mastering DFS and BFS: Level-order traversals, topological sorting (Webpack bundle resolution), and cycle detection.
• Binary Search on Answer Spaces: How to solve Hard problems (like Median of Two Sorted Arrays or Split Array Largest Sum) using binary search without looking at a simple sorted array.