Fresher · Linked lists

Reverse a Singly Linked List

Nodes have shape {value, next}; the final next is null. Return a reversed list using new nodes and preserve the original list. Values are numbers and the input has no cycles.

Examples

1 → 2 → 3 → null becomes 3 → 2 → 1 → null

Compare approaches

Collect then rebuild

Store all values before building the reverse. This makes the traversal easy to inspect.

Time: O(n) · Space: O(n) auxiliary plus O(n) output

function reverseList(head) { const values = []; for (let node = head; node; node = node.next) values.push(node.value); let result = null; for (const value of values) result = {value, next: result}; return result; }

Prepend during traversal

A new node points to the previously built prefix. No temporary values array is needed; new nodes preserve the original.

Time: O(n) · Space: O(1) auxiliary plus O(n) output

function reverseList(head) {
  let result = null;
  for (let node = head; node; node = node.next) result = {value: node.value, next: result};
  return result;
}

Common traps

The no-mutation contract requires new nodes.
Do not label total space O(1): the returned list occupies O(n).

Practise in the workspace →