SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 26
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 26 of 30

Linked list questions

build a list with classesreverse itfind the middle (slow/fast pointers)detect a cycle

These are the notes for JavaScript Coding Questions, episode 26, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Last episode was searching and sorting. Today: linked lists, the data structure interviewers love to ask about. JavaScript has no built-in linked list, so first we build one with a class. Then three classic questions: reverse it, find the middle node in one pass with slow and fast pointers, and detect a cycle, first with a Set and then with Floyd's tortoise and hare in O(1) extra space. On the way we meet TypeError: train.reverse is not a function, a reverse that loses most of the list, Cannot read properties of null, a Set that gives the wrong answer, and Converting circular structure to JSON.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. When a program crashes, we show the real first lines of the error, up to the error message; after that Node prints about ten lines starting with at (where the error happened) and its version, which we cut. The first line of an error is the file and line number; on your computer you will see your own path.

First: what is a linked list?

Think of a train. Each coach carries passengers, and a coupling that hooks it to the next coach. The engine is where you start. To reach coach three, you walk from the engine, coach by coach: you can't jump straight to it. The last coach has nothing behind it.

  • Node: one coach. An object with two properties: a value (the passengers, any data) and next (the coupling).
  • next: a reference to the next node, that is, the next node object itself, not a copy of it. Two variables, or a variable and a next, can point to the same object in memory.
  • Head: the first node (the engine). If you have the head, you can reach every node. If you lose it, the list is gone.
  • Tail: the last node. Its next is null, JavaScript's value for "nothing here". That's how we know the list has ended.
  • Empty list: no nodes at all. The head itself is null.
  • Linked list: nodes chained together by next, from the head to null. (This one is a singly linked list: each node knows only the next one, not the previous one.)

Build it with a class

A class is a template for objects; its constructor runs when you write new Node(...) and stores the values on this, the new object. next = null is a default parameter: if we leave next out, it's null.

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}
const s3 = new Node("S3");
const s2 = new Node("S2", s3);
const train = new Node("Engine", new Node("S1", s2));
console.log(train);
Node {
  value: 'Engine',
  next: Node { value: 'S1', next: Node { value: 'S2', next: [Node] } }
}

Node inside node inside node: the engine's next is S1, whose next is S2. Deeper than two levels, console.log stops and prints just [Node], so we can't see S3. We need a better way to print a list.

Two helpers, and the obvious reverse()

Building by hand gets long, so every later program starts with two small helpers:

  • fromArray(vals) builds a list from an array, back to front. reduceRight walks the array from the last item to the first, carrying a value along: it starts with null (the end of the list), and for each value makes new Node(v, next) in front of what it has so far. [1, 2, 3] becomes 3 -> null, then 2 -> 3 -> null, then 1 -> 2 -> 3 -> null.
  • show(head) walks the list and prints the arrows. for (let n = head; n; n = n.next) is the linked list loop: start at the head, stop when n is null (null is falsy), and step with n = n.next.

And then the obvious way to reverse a train: call .reverse(), like on an array.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
const train = fromArray(["Engine", "S1", "S2", "S3"]);
console.log(show(train));
console.log(train.reverse());
Engine -> S1 -> S2 -> S3 -> null
/home/user/main.js:15
console.log(train.reverse());
                  ^

TypeError: train.reverse is not a function

show works: Engine -> S1 -> S2 -> S3 -> null. But then: TypeError: train.reverse is not a function (a TypeError is JavaScript's error for using a value the wrong way, here calling something that isn't a function). Why? train is a Node object, not an array. It has only value and next. Arrays get reverse, map, length and the rest from Array.prototype, the shared object every array inherits its methods from. Our list gets nothing for free: we write every operation ourselves.

Walking costs steps; adding at the front doesn't

To read position 3, an array jumps straight there: coaches[3]. A list has to walk 3 steps from the head. But adding a coach in front is one line: a new node whose next is the old head.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function at(head, index) {
  let n = head, steps = 0;
  while (n && steps < index) {
    n = n.next;
    steps++;
  }
  return (n ? n.value : undefined) + " (steps: " + steps + ")";
}
const coaches = ["Engine", "S1", "S2", "S3"];
const train = fromArray(coaches);
console.log("array index 3:", coaches[3]);
console.log("list position 3:", at(train, 3));
console.log("list position 9:", at(train, 9));
const longer = new Node("Guard", train);
console.log(show(longer));
console.log(show(train));
array index 3: S3
list position 3: S3 (steps: 3)
list position 9: undefined (steps: 4)
Guard -> Engine -> S1 -> S2 -> S3 -> null
Engine -> S1 -> S2 -> S3 -> null
  • Position 3 is S3 after 3 steps. Position 9 doesn't exist: the walk falls off the end after 4 steps and gives undefined.
  • new Node("Guard", train) puts a guard's coach in front without touching any other node. train still points to the engine, so show(train) is unchanged: two heads now share the same four coaches.
Array Linked list
Read item i arr[i]: one step, O(1) walk i nodes from the head: O(n)
Add at the front unshift moves every item: O(n) new Node(v, head): O(1)
Add at the end push: O(1) walk to the tail: O(n), or O(1) if you keep a tail reference
Insert or delete once you're at the spot move every later item: O(n) change one or two next references: O(1)
Length .length count it yourself (or keep a counter)
Built-in methods reverse, map, sort, includes, … none
In memory items side by side in one block separate node objects, linked by references

(Big-O describes how the work grows as the input grows: O(1) means "the same, whatever the size"; O(n) means "in step with n", the number of nodes.)

Q1: Reverse a linked list

Problem. Write reverse(head): Engine -> S1 -> S2 -> S3 -> null becomes S3 -> S2 -> S1 -> Engine -> null. Return the new head.

Think out loud. - In place: don't build a new list, just flip every next arrow so it points backwards. No extra list, only a few variables. - Real life: the train reaches the last station and goes back the other way. The last coach becomes the front. - We need two pointers: curr, the node we're flipping, and prev, the node behind it (where its arrow should point now). The first node's arrow points to null: it becomes the tail. - Edge cases: a list with one node, and an empty list (null).

Attempt: flip, then step forward

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    curr.next = prev;
    prev = curr;
    curr = curr.next;
  }
  return prev;
}
console.log(show(reverse(fromArray(["Engine", "S1", "S2", "S3"]))));
Engine -> null

Engine -> null. Only one coach. S1, S2 and S3 are gone. Why? Look at the order. curr.next = prev runs first, and that overwrites the only link to the rest of the train. So when we then move with curr = curr.next, we go to the new next, which is prev: null. The loop ends after one node, and nothing points to S1 any more. (JavaScript frees nodes nobody can reach. That's garbage collection. So the rest of the train is really lost.)

Fix: save next first

A railway worker re-couples the train coach by coach. Before unhooking a coach, they hold on to the next one with a rope, so it can't roll away.

  1. Save next: const next = curr.next (hold the rope).
  2. Flip: curr.next = prev (hook this coach backwards, to the one behind it).
  3. Move: prev = curr; curr = next (step forward to the coach you held).
  4. New head: when curr is null, there are no coaches left, and prev is the last one we flipped. Return it.
class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function reverse(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
console.log(show(reverse(fromArray(["Engine", "S1", "S2", "S3"]))));
console.log(show(reverse(fromArray([7]))), "|", show(reverse(null)));
S3 -> S2 -> S1 -> Engine -> null
7 -> null | null

S3 -> S2 -> S1 -> Engine -> null. One node stays 7 -> null. Reversing null gives null, because the loop never runs and prev is still null.

Complexity: each node is visited once, so O(n) time. Only three variables (prev, curr, next), whatever the length: O(1) extra space. That's why interviewers want the in-place version and not "copy the values into an array and rebuild".

Q2: Find the middle node

Problem. Write middle(head) and return the middle node's value. 1 2 3 4 5 → 3. 1 2 3 4 5 6 has two middles, 3 and 4; the usual rule is the second one: 4.

Think out loud. - There's no length property and no index, so we have to walk. - The interviewer adds: in one pass. - Edge cases: one node, and an empty list.

Attempt: count, then walk half

Count the nodes first, then walk again, Math.floor(length / 2) steps (Math.floor rounds down to a whole number). We count steps too.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function middle(head) {
  let length = 0, steps = 0;
  for (let n = head; n; n = n.next) { length++; steps++; }
  let n = head;
  for (let i = 0; i < Math.floor(length / 2); i++) {
    n = n.next; steps++;
  }
  return n.value + " (steps: " + steps + ")";
}
console.log(middle(fromArray([1, 2, 3, 4, 5])));
console.log(middle(fromArray([1, 2, 3, 4, 5, 6])));
console.log(middle(null));
3 (steps: 7)
4 (steps: 9)
/home/user/main.js:20
  return n.value + " (steps: " + steps + ")";
           ^

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

3 and 4, correct, but 7 and 9 steps: the list is walked one and a half times (5 + 2, 6 + 3). And the empty list: TypeError: Cannot read properties of null (reading 'value'). Why? Two passes, and no check for an empty list: n starts as null, the loop doesn't run, and n.value reads a property of null, which always throws. We need one walk that stops exactly halfway, and that handles null.

Fix: slow and fast pointers

Two friends start at the engine of a long train. One walks one coach at a time, the other runs two coaches at a time, twice the speed. When the runner reaches the end of the train, the walker has covered exactly half the distance: the walker is standing at the middle coach. One walk, no counting. These are called slow and fast pointers (two variables that move through the same list at different speeds).

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function middle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow ? slow.value : null;
}
console.log(middle(fromArray([1, 2, 3, 4, 5])));
console.log(middle(fromArray([1, 2, 3, 4, 5, 6])));
console.log(middle(fromArray([9])), middle(null));
3
4
9 null

3, 4, 9 and null: no crash.

  • On 5 nodes: slow goes 1 → 2 → 3 while fast goes 1 → 3 → 5. Fast's next is null, so we stop: slow is at 3.
  • On 6 nodes: fast goes 1 → 3 → 5 → null (it falls off the end) just as slow reaches 4, the second middle.
  • Why the loop checks both, in this order. fast.next.next needs fast.next to exist, and fast.next needs fast to exist. && stops at the first falsy value (that's short-circuit evaluation), so fast && fast.next never reads a property of null. Swap them and it crashes (see the common mistakes).
  • slow ? slow.value : null (the ternary operator, "if slow, its value, else null") handles the empty list.

Complexity: one pass, about n / 2 loop turns, so O(n) time and O(1) space.

Q3: Detect a cycle

Problem. Write hasCycle(head): true if the list loops, false if it ends.

Think out loud. - A cycle means some node's next points back to an earlier node. In A -> B -> C -> B -> C -> B …, C's next is B again. Walk this list and you never reach null. - Real life: a circular bus route with no last stop. - Edge cases: a round trip like Pune -> Mumbai -> Pune, which visits a name twice but does end; a node that points to itself; and null.

Attempt: remember every stop name in a Set

A Set is a collection that keeps only unique values; seen.has(x) asks "is x in it?", and seen.add(x) adds it. If we see a name again, call it a loop.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
function hasCycle(head) {
  const seen = new Set();
  for (let n = head; n; n = n.next) {
    if (seen.has(n.value)) return true;
    seen.add(n.value);
  }
  return false;
}
const a = new Node("A"), b = new Node("B"), c = new Node("C");
a.next = b; b.next = c; c.next = b; // C goes back to B
console.log(hasCycle(a));
const trip = new Node("Pune", new Node("Mumbai", new Node("Pune")));
console.log(hasCycle(trip));
true
true

true for the loop, correct. But true for Pune -> Mumbai -> Pune too, and that trip ends: there's no cycle. Why? Two different stops can have the same name. A cycle is about the same node, the same object in memory, not the same value.

Better: store the nodes themselves

A Set compares objects by reference: two different Node objects are two different entries, even if their values are equal. Only the very same object counts as "seen".

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const first = new Node("Pune"), last = new Node("Pune");
console.log(first.value === last.value, first === last);
const names = new Set([first.value, last.value]);
const nodes = new Set([first, last]);
console.log(names.size, nodes.size, nodes.has(first), nodes.has(new Node("Pune")));
const same = first;
console.log(same === first, (same.value = "Pune Jn", first.value));
true false
1 2 true false
true Pune Jn
  • first.value === last.value is true, but first === last is false: same name, two objects.
  • A Set of the names has 1 entry; a Set of the nodes has 2. A brand-new Node("Pune") is not in it.
  • same = first doesn't copy: both variables reference one object, so changing same.value changes first.value too. (The comma in (a, b) runs both and gives b.)

So change seen.has(n.value) to seen.has(n) and seen.add(n.value) to seen.add(n):

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
function hasCycle(head) {
  const seen = new Set();
  for (let n = head; n; n = n.next) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
const a = new Node("A"), b = new Node("B"), c = new Node("C");
a.next = b; b.next = c; c.next = b; // C goes back to B
console.log(hasCycle(a));
const trip = new Node("Pune", new Node("Mumbai", new Node("Pune")));
console.log(hasCycle(trip));
true
false

true, false. Correct. But the Set grows with every node we visit: O(n) extra memory. The interviewer asks: can you do it with O(1)?

Fix: Floyd's tortoise and hare

The same two pointers, on a running track. A slow runner, the tortoise, takes one step; a fast runner, the hare, takes two.

  • If the road is straight, the hare simply reaches the end (null). They never meet again. No cycle.
  • On a circular track, the hare keeps going round and gains one step on the tortoise every turn. Sooner or later it catches up, and they stand on the same node. That's Floyd's cycle detection.
class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
const a = new Node("A"), b = new Node("B"), c = new Node("C");
a.next = b; b.next = c; c.next = b; // C goes back to B
console.log(hasCycle(a));
const trip = new Node("Pune", new Node("Mumbai", new Node("Pune")));
console.log(hasCycle(trip));
const x = new Node("X"); x.next = x;
console.log(hasCycle(x), hasCycle(null));
true
false
true false

true for the A B C loop, false for the round trip, true for X pointing to itself, false for null. slow === fast compares references: "are they the same node?", exactly what the Set of nodes did, without the Set.

Complexity: with no loop, fast reaches the end in about n / 2 steps. With a loop, once both are inside it, the gap between them shrinks by one every step, so they meet within one more lap. O(n) time, and only two variables: O(1) space.

One more trap: printing a looping list as JSON

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const a = new Node("A"), b = new Node("B"), c = new Node("C");
a.next = b; b.next = c; c.next = b;
console.log(JSON.stringify(a));
/home/user/main.js:8
console.log(JSON.stringify(a));
                 ^

TypeError: Converting circular structure to JSON
    --> starting at object with constructor 'Node'
    |     property 'next' -> object with constructor 'Node'
    --- property 'next' closes the circle

TypeError: Converting circular structure to JSON. JSON.stringify follows every next; on a loop that would go on forever, so it notices it's back at an object it's already inside and throws. Node even draws the circle: from A, property next to B, and next (C's) closes the circle. Printing, copying or saving a list with a loop needs care: detect the cycle first. (console.log doesn't throw: it prints <ref *1> and [Circular *1]; see the common mistakes.)

Going further

Reverse with recursion

The reverse of a list is: reverse everything after the head, then hang the old head on the end. After reverseRec(head.next), head.next is the last node of the reversed part, so head.next.next = head hooks the old head behind it, and head.next = null makes it the new tail. Base case: an empty list or a single node is already reversed.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function reverseRec(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverseRec(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}
console.log(show(reverseRec(fromArray(["Engine", "S1", "S2", "S3"]))));
console.log(show(reverseRec(fromArray([7]))), "|", show(reverseRec(null)));
const big = fromArray(Array.from({ length: 100000 }, (_, i) => i));
try {
  reverseRec(big);
} catch (err) {
  console.log(err.constructor.name + ":", err.message);
}
S3 -> S2 -> S1 -> Engine -> null
7 -> null | null
RangeError: Maximum call stack size exceeded

Same results for 4 nodes, one node and null. But every call waits on the call stack (the list of calls that have started but not finished), so the recursion is O(n) deep: a 100,000-node list throws RangeError: Maximum call stack size exceeded (episode 24). The loop version has no such limit. In an interview, write the loop, and mention the recursive one.

A LinkedList class with append, size and toArray

Real code wraps the nodes in a class that keeps the head, a tail reference (so append doesn't have to walk the whole list) and a size counter (so size doesn't have to count).

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
class LinkedList {
  #size = 0;
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(value) {
    const node = new Node(value);
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
    this.#size++;
    return this;
  }
  prepend(value) {
    this.head = new Node(value, this.head);
    if (!this.tail) this.tail = this.head;
    this.#size++;
    return this;
  }
  get size() {
    return this.#size;
  }
  *[Symbol.iterator]() {
    for (let n = this.head; n; n = n.next) yield n.value;
  }
  toArray() {
    return [...this];
  }
  toString() {
    return [...this, "null"].join(" -> ");
  }
}
const train = new LinkedList();
train.append("S1").append("S2").append("S3").prepend("Engine");
console.log(String(train));
console.log(train.size, train.toArray());
console.log(train.head.value, train.tail.value);
for (const coach of train) console.log("boarding", coach);
console.log(new LinkedList().size, new LinkedList().toArray(), String(new LinkedList()));
Engine -> S1 -> S2 -> S3 -> null
4 [ 'Engine', 'S1', 'S2', 'S3' ]
Engine S3
boarding Engine
boarding S1
boarding S2
boarding S3
0 [] null
  • append hooks the new node after the tail and moves the tail; on an empty list the new node is both head and tail. prepend puts it in front. Both are O(1).
  • #size is a private field: only code inside the class can read or change it. get size() is a getter: read it like a property, train.size, without ().
  • return this lets you chain calls: train.append("S1").append("S2").
  • *[Symbol.iterator]() is a generator method (the * and yield) that hands out the values one by one. It makes the list iterable, so for...of, the spread [...this] and therefore toArray() all work.
  • String(train) calls our toString(). The empty list: size 0, [], and just null.

Find where the cycle starts

hasCycle says whether there's a loop. The follow-up question: at which node does it start? After the tortoise and hare meet, put a new pointer p at the head and move p and slow one step each: they meet exactly at the start of the loop. (Why: if the loop start is k steps from the head, then walking k steps forward from the meeting point also lands on the loop start, maybe after some full laps. Draw it with 6 nodes to convince yourself.) Then walk once round the loop from any node in it to measure its length.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
function cycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
}
function cycleLength(meet) {
  let len = 1;
  for (let n = meet.next; n !== meet; n = n.next) len++;
  return len;
}
const stops = ["Depot", "A", "B", "C", "D", "E"].map((v) => new Node(v));
for (let i = 0; i < stops.length - 1; i++) stops[i].next = stops[i + 1];
stops[5].next = stops[2]; // E goes back to B
const start = cycleStart(stops[0]);
console.log("loop starts at", start.value, "length", cycleLength(start));
const x = new Node("X"); x.next = x;
console.log(cycleStart(x).value, cycleLength(x));
const line = new Node("P", new Node("Q", new Node("R")));
console.log(cycleStart(line), cycleStart(null));
loop starts at B length 4
X 1
null null

Depot, A, B, C, D, E, and E goes back to B: the loop starts at B and has 4 nodes (B, C, D, E). A node pointing to itself: the loop starts at X, length 1. A list that ends, and null: no loop start, null. Still O(n) time and O(1) space. (map here makes an array of six nodes; we then link them by hand.)

Delete a node by value, and count the length

To delete a node, make the node before it skip over it: prev.next = prev.next.next (that's the quiz). The head has no node before it, so it's a special case: return head.next as the new head. And since a list has no length property, length(head) counts the nodes while walking.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function length(head) {
  let count = 0;
  for (let n = head; n; n = n.next) count++;
  return count;
}
function remove(head, value) {
  if (head === null) return null;
  if (head.value === value) return head.next;
  let prev = head;
  while (prev.next && prev.next.value !== value) prev = prev.next;
  if (prev.next) prev.next = prev.next.next;
  return head;
}
let train = fromArray(["Engine", "S1", "S2", "S3"]);
console.log(show(train), "length", length(train), "| train.length is", train.length);
train = remove(train, "S2");
console.log(show(train), "length", length(train));
train = remove(train, "Engine");
console.log(show(train), "length", length(train));
train = remove(train, "S3");
console.log(show(train), "length", length(train));
console.log(show(remove(train, "AC1")), "|", show(remove(null, "S1")), "length", length(null));
Engine -> S1 -> S2 -> S3 -> null length 4 | train.length is undefined
Engine -> S1 -> S3 -> null length 3
S1 -> S3 -> null length 2
S1 -> null length 1
S1 -> null | null length 0

train.length is undefined: a node has only value and next. Then S2 is removed, then the engine (the head changes, so we must use the returned head: train = remove(...)), then S3 (the tail). A value that isn't there ("AC1") leaves the list unchanged, and null stays null. Walking with prev.next instead of curr means we always stop one node before the one to delete. O(n) to find it, O(1) to unlink it. Counting is O(n) too; the LinkedList class above keeps a counter instead, so its size is O(1).

Complexity summary

Function Time Extra space
at(head, i): read position i O(n) O(1)
new Node(v, head): add at the front O(1) O(1)
append with a tail reference O(1) O(1)
reverse(head) with a loop O(n) O(1)
reverseRec(head) O(n) O(n) call stack: overflows near 100,000 nodes
middle by counting, then walking half O(n), about 1.5 n steps O(1)
middle with slow and fast pointers O(n), one pass O(1)
hasCycle with a Set of values O(n), but wrong for repeated values O(n)
hasCycle with a Set of nodes O(n) O(n)
hasCycle, Floyd's tortoise and hare O(n) O(1)
cycleStart (Floyd, then from the head) O(n) O(1)
remove(head, value) O(n) O(1)
removeFromEnd(head, n) (your turn) O(n), one pass O(1)

Common mistakes (and the exact outputs)

Every output in the table comes from a real run. Two of the extra traps, in full:

Forgetting new:

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const engine = Node("Engine");
/home/user/main.js:6
const engine = Node("Engine");
               ^

TypeError: Class constructor Node cannot be invoked without 'new'

Printing a looping list: a show-style walk would never end (here we stop it after 12 steps), while console.log marks the loop instead of throwing:

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const a = new Node("A"), b = new Node("B"), c = new Node("C");
a.next = b; b.next = c; c.next = b;
let s = "", steps = 0;
for (let n = a; n && steps < 12; n = n.next, steps++) s += n.value + " -> ";
console.log(s + "... (stopped after " + steps + " steps)");
console.log(a);
A -> B -> C -> B -> C -> B -> C -> B -> C -> B -> C -> B -> ... (stopped after 12 steps)
Node {
  value: 'A',
  next: <ref *1> Node {
    value: 'B',
    next: Node { value: 'C', next: [Circular *1] }
  }
}
Mistake Code What you see Why Fix
Array methods on a list train.reverse() TypeError: train.reverse is not a function a Node is not an array write reverse(head) yourself
Flip before saving next curr.next = prev; … curr = curr.next Engine -> null the only link to the rest is overwritten const next = curr.next first
Return the old head return head after reversing Engine -> null the old head is now the tail return prev
Use the old variable after an in-place reverse show(list) Engine -> null list still points to the old head, now the tail use the returned head
No empty-list check n.value with head = null TypeError: Cannot read properties of null (reading 'value') the head is null check null first: slow ? slow.value : null
Wrong order in the loop check while (fast.next && fast) TypeError: Cannot read properties of null (reading 'next') on 6 nodes fast is already null while (fast && fast.next)
Values instead of nodes seen.has(n.value) true for Pune -> Mumbai -> Pune same name ≠ same node seen.has(n), or Floyd
Calling the class without new Node("Engine") TypeError: Class constructor Node cannot be invoked without 'new' a class can only be called with new new Node("Engine")
Moving the head while walking train = train.next in a loop coaches: 4, then null the only reference to the engine is gone walk with a separate n
JSON on a loop JSON.stringify(a) with c.next = b TypeError: Converting circular structure to JSON it would never end detect the cycle first
A walk on a loop for (let n = a; n; n = n.next) with a cycle never ends; with a 12-step limit: A -> B -> C -> B -> C -> B -> … null is never reached hasCycle first, or a step limit
Recursion on a long list reverseRec on 100,000 nodes RangeError: Maximum call stack size exceeded O(n) stack depth use the loop

Mini project: a road-trip playlist

A music app keeps a playlist as a linked list: each song knows the next one. Repeat mode links the last song back to the first, which is a cycle on purpose. Everything from today in one class: append with a tail, an in-place reverse, Floyd's check, and a toJSON that's safe on a loop. (If an object has a toJSON() method, JSON.stringify saves what it returns instead of following its properties.)

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
class Playlist {
  constructor(titles = []) {
    this.head = null;
    this.tail = null;
    for (const t of titles) this.add(t);
  }
  add(title) {
    const node = new Node(title);
    if (this.tail) this.tail.next = node;
    else this.head = node;
    this.tail = node;
  }
  hasLoop() {
    let slow = this.head, fast = this.head;
    while (fast && fast.next) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow === fast) return true;
    }
    return false;
  }
  setRepeat(on) {
    if (this.tail) this.tail.next = on ? this.head : null;
  }
  play(max) {
    const out = [];
    for (let n = this.head; n && out.length < max; n = n.next) out.push(n.value);
    return out.join(", ");
  }
  reverse() {
    if (this.hasLoop()) throw new Error("turn repeat off before reversing");
    let prev = null, curr = this.head;
    this.tail = this.head;
    while (curr) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    this.head = prev;
  }
  toJSON() {
    if (this.hasLoop()) return { repeat: true, first: this.head.value };
    const songs = [];
    for (let n = this.head; n; n = n.next) songs.push(n.value);
    return { repeat: false, songs };
  }
}
const trip = new Playlist(["Kesariya", "Ilahi", "Safarnama", "Kun Faya Kun", "Phir Se Ud Chala"]);
console.log("play:", trip.play(10));
trip.reverse();
console.log("reversed:", trip.play(10));
console.log("tail is now:", trip.tail.value);
trip.setRepeat(true);
console.log("repeat on, loop?", trip.hasLoop());
console.log("first 7:", trip.play(7));
try {
  trip.reverse();
} catch (err) {
  console.log("Error:", err.message);
}
console.log(JSON.stringify(trip));
trip.setRepeat(false);
console.log("repeat off, loop?", trip.hasLoop());
console.log(JSON.stringify(trip));
const empty = new Playlist();
console.log(empty.hasLoop(), JSON.stringify(empty));
play: Kesariya, Ilahi, Safarnama, Kun Faya Kun, Phir Se Ud Chala
reversed: Phir Se Ud Chala, Kun Faya Kun, Safarnama, Ilahi, Kesariya
tail is now: Kesariya
repeat on, loop? true
first 7: Phir Se Ud Chala, Kun Faya Kun, Safarnama, Ilahi, Kesariya, Phir Se Ud Chala, Kun Faya Kun
Error: turn repeat off before reversing
{"repeat":true,"first":"Phir Se Ud Chala"}
repeat off, loop? false
{"repeat":false,"songs":["Phir Se Ud Chala","Kun Faya Kun","Safarnama","Ilahi","Kesariya"]}
false {"repeat":false,"songs":[]}
  • reverse() is the Q1 loop; the old head becomes the new tail, so we update this.tail too: Kesariya.
  • setRepeat(true) sets tail.next = head: now hasLoop() is true, and play(7) goes round the list once and keeps going. The max limit is what stops it.
  • reverse() refuses to run on a loop (it would never reach null), and throws an Error we catch.
  • JSON.stringify(trip) with repeat on doesn't throw: our toJSON sees the loop and returns a small summary instead of walking forever. With repeat off, it saves the songs.
  • The empty playlist: no loop, no songs.

Your turn: remove the n-th node from the end (solution)

Problem. Write removeFromEnd(head, n): remove the n-th coach counting from the back, and return the head. Engine -> S1 -> S2 -> S3, n = 2 → Engine -> S1 -> S3. One pass.

Hint from the video: two pointers again. Move fast n steps ahead first, then move both together until fast reaches the end. And think about n equal to the length: that removes the head.

The idea. If fast is n nodes ahead of slow, then when fast is on the last node, slow is on the node just before the one to remove, so slow.next = slow.next.next unlinks it.

The dummy node. When n is the length, the node to remove is the head, and there's no node before it. So we put a dummy node (a fake extra node, sometimes called a sentinel) in front of the head and start both pointers there. Now every real node, the head included, has a node before it. At the end we return dummy.next, the real head, which may have changed.

class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function removeFromEnd(head, n) {
  const dummy = new Node("dummy", head);
  let fast = dummy, slow = dummy;
  for (let i = 0; i < n; i++) {
    if (fast.next === null) return head; // n is bigger than the length
    fast = fast.next;
  }
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}
const make = () => fromArray(["Engine", "S1", "S2", "S3"]);
console.log(show(removeFromEnd(make(), 2)));
console.log(show(removeFromEnd(make(), 1)));
console.log(show(removeFromEnd(make(), 4)));
console.log(show(removeFromEnd(make(), 9)));
console.log(show(removeFromEnd(fromArray(["Engine"]), 1)));
Engine -> S1 -> S3 -> null
Engine -> S1 -> S2 -> null
S1 -> S2 -> S3 -> null
Engine -> S1 -> S2 -> S3 -> null
null
  • n = 2: fast goes 2 steps (to S1), then both move until fast is on S3; slow is on S1, so S2 is skipped: Engine -> S1 -> S3 -> null.
  • n = 1 removes the tail, S3.
  • n = 4 = the length: fast reaches S3 in 4 steps and doesn't move again; slow is still on the dummy, so the head is removed: S1 -> S2 -> S3 -> null.
  • n = 9 is more than the length: fast runs out of nodes, and we return the list unchanged. (Some versions throw an error instead; ask the interviewer.)
  • A one-node list with n = 1 becomes empty: null.

Without the dummy (both pointers start at head, and the function returns head), the obvious version works for n = 2, then crashes when n is the length: fast walks off the end to null, and the while (fast.next) check throws TypeError: Cannot read properties of null (reading 'next').

Complexity: one pass, O(n) time; two pointers and one dummy node, O(1) space.

Practice questions (with solutions)

1. Merge two sorted linked lists. 1 -> 4 -> 7 and 2 -> 3 -> 8 -> 9 → 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9. Reuse the nodes; don't create new ones.

Solution
class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function merge(a, b) {
  const dummy = new Node("dummy");
  let tail = dummy;
  while (a && b) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}
console.log(show(merge(fromArray([1, 4, 7]), fromArray([2, 3, 8, 9]))));
console.log(show(merge(fromArray([5]), null)), "|", show(merge(null, null)));
console.log(show(merge(fromArray([1, 1, 2]), fromArray([1, 3]))));
1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> null
5 -> null | null
1 -> 1 -> 1 -> 2 -> 3 -> null

A dummy node again, so the first node needs no special case. tail is the last node of the merged list; at each step we hook the smaller of the two front nodes onto it. When one list runs out, the rest of the other is already sorted, so hook it on in one go: a ?? b (the nullish coalescing operator: a, unless a is null or undefined, then b). <= keeps equal values in their original order. O(n + m) time, O(1) space.

2. Is a linked list a palindrome? A palindrome reads the same both ways: r a c e c a r, 1 2 2 1. O(1) extra space.

Solution
class Node {
  constructor(value, next = null) {
    this.value = value; this.next = next;
  }
}
const fromArray = (vals) =>
  vals.reduceRight((next, v) => new Node(v, next), null);
function show(head) {
  let s = "";
  for (let n = head; n; n = n.next) s += n.value + " -> ";
  return s + "null";
}
function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let prev = null, curr = slow;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  for (let left = head, right = prev; right; left = left.next, right = right.next) {
    if (left.value !== right.value) return false;
  }
  return true;
}
console.log(isPalindrome(fromArray([..."racecar"])));
console.log(isPalindrome(fromArray([1, 2, 2, 1])));
console.log(isPalindrome(fromArray([1, 2, 3])));
console.log(isPalindrome(fromArray([7])), isPalindrome(null));
true
true
false
true true

All three ideas from today: find the middle with slow and fast, reverse the second half in place, then walk from both ends and compare. [..."racecar"] spreads a string into an array of letters. The right half is never longer than the left, so we stop when right is null. O(n) time, O(1) space. Note that it changes the list (the second half stays reversed); reverse it back if the caller still needs it.

Quick quiz

class Node {
  constructor(v, next = null) { this.v = v; this.next = next; }
}
const list = new Node(1, new Node(2, new Node(3)));
list.next = list.next.next;
let s = "";
for (let n = list; n; n = n.next) s += n.v;
console.log(s);

A) 123 B) 13 C) 12 D) 3

Answer
13

B. list.next was node 2; list.next = list.next.next makes it point straight to node 3. Node 2 is skipped, so the walk joins 1, then 3: "13" (s += n.v adds the numbers to a string, so they're joined, not added). This is exactly how you delete a node from a linked list.

Interview questions

  1. What is a linked list? A chain of nodes, each holding a value and a reference (next) to the next node. The first node is the head; the last node's next is null.
  2. Linked list or array? An array reads any index in O(1). A linked list needs O(n) to reach position i, but adds or removes at the front (or anywhere you already are) in O(1), without moving other items.
  3. Why can't you call .reverse() on a linked list? It isn't an array: a node has only value and next, so train.reverse is not a function. You write every operation yourself.
  4. How do you reverse a linked list in place? Keep prev and curr; for each node save next, flip curr.next = prev, move both forward; return prev. O(n) time, O(1) space.
  5. What goes wrong if you flip before saving next? You overwrite the only link to the rest of the list: you get Engine -> null.
  6. How do you find the middle in one pass? Slow moves 1 step, fast moves 2; when fast reaches the end, slow is at the middle. Loop while fast && fast.next.
  7. How do you detect a cycle? Store visited nodes in a Set (O(n) space), or Floyd's tortoise and hare: if slow and fast ever reference the same node, there's a loop (O(1) space).
  8. Why not store values in the Set? Different nodes can have the same value (Pune -> Mumbai -> Pune): you'd report a cycle that doesn't exist.
  9. Why do slow and fast always meet in a loop? Inside the loop, fast gains one node on slow every step, so the gap shrinks by one until it's zero: they can't jump over each other.
  10. What is a dummy node for? A fake node in front of the head, so removing or adding at the head needs no special case. Return dummy.next.

Glossary

Term Meaning
Linked list Nodes chained together by next references, from the head to null
Singly linked list A linked list where each node knows only the next node, not the previous one
Node One element of a linked list: a value and a next
Value The data a node carries (a coach's passengers)
next A node's reference to the following node; null on the last node
Head The first node; the only way into the list
Tail The last node; its next is null
null JavaScript's value for "nothing here": the end of a list, or an empty list
Empty list A list with no nodes; its head is null
Reference How objects are stored: a variable or next points to an object, it doesn't hold a copy. Two references can point to the same node
=== on objects true only if both sides reference the very same object
class / constructor / new A template for objects / the method that sets up a new object / the keyword that creates one
this Inside a constructor or method, the object it's working on
Default parameter A value a parameter gets when the caller leaves it out: next = null
Array.prototype The shared object arrays inherit reverse, map and the rest from
reduceRight Walks an array from the last item to the first, carrying one value along
Traversal Walking a list from the head, node by node: for (let n = head; n; n = n.next)
In place Changing the existing nodes instead of building a new list; O(1) extra space
prev / curr / next The three pointers of the reverse: the node behind, the node we're flipping, the node ahead
Garbage collection JavaScript freeing objects nothing references any more (the lost coaches)
Pointer In these notes, a variable that refers to a node and moves along the list (slow, fast, prev)
Slow and fast pointers Two pointers moving at 1 and 2 nodes per step; used for the middle and for cycles
Short-circuit evaluation a && b stops at a if it's falsy, so fast && fast.next never reads null.next
Ternary operator cond ? a : b: a if cond is true, else b
Cycle (loop) Some node's next points back to an earlier node, so the list never reaches null
Set A collection of unique values; objects are compared by reference
Floyd's tortoise and hare Cycle detection with a slow and a fast pointer: they meet only if there's a loop. O(n) time, O(1) space
Cycle start The first node of the loop, found by moving a pointer from the head and one from the meeting point together
Circular structure An object that, by following its properties, leads back to itself; JSON.stringify refuses it
JSON.stringify / toJSON Turns a value into JSON text / a method that tells it what to save instead
<ref *1> / [Circular *1] How console.log marks an object and the place that points back to it
Dummy node (sentinel) A fake node before the head, so the head needs no special case
Private field (#size) A property only code inside the class can use
Getter (get size()) A method you read like a property, without ()
Generator / Symbol.iterator A * function that yields values one by one / the method that makes an object work with for...of and ...
Iterable An object you can loop over with for...of or spread with ...
Spread (...) Spreads out the values of an iterable: [...this], [..."racecar"]
Nullish coalescing (??) a ?? b is a, unless a is null or undefined, then b
Recursion / call stack A function calling itself / the list of calls still waiting; too deep gives RangeError
TypeError JavaScript's error for using a value the wrong way: calling a non-function, reading a property of null, a class without new, a circular structure
RangeError JavaScript's error for a size out of range, including "Maximum call stack size exceeded"
Big-O, O(1), O(n) How the work grows with the input: the same whatever the size / in step with the number of nodes
Palindrome Reads the same forwards and backwards

Summary

  • A node is a value plus next; the head is the first node, and the last node's next is null. A linked list is not an array: no reverse(), no index, no length. You write every operation.
  • Lists are O(n) to reach position i, but O(1) to add at the front or to unlink a node once you're beside it.
  • Reverse in place: save next, flip curr.next = prev, move on, return prev. O(n), O(1). Flip before saving and you lose the list (Engine -> null).
  • Middle in one pass with slow and fast pointers; loop while fast && fast.next, in that order, and handle the empty list.
  • Cycle: compare nodes, not values. A Set of nodes works in O(n) space; Floyd's tortoise and hare does it in O(1): slow === fast means a loop. A looping list breaks JSON.stringify and every plain walk.
  • A dummy node removes the special case for the head (your turn: remove the n-th node from the end).
  • Next episode: stack and queue questions: a stack that knows its minimum, a queue built from two stacks, and the next greater element.