Reverse a linked list

Easy TimeO(n) SpaceO(1)

A singly linked list only points forwards: there is no index into it and no way back. Given the head of one, reverse it and return the new head, so [1, 2, 3, 4, 5] becomes [5, 4, 3, 2, 1]. Each node holds a value and a single pointer, and the reversal has to come from re-pointing the existing nodes rather than from building a new list. An empty list and a one-node list are already reversed.

Examples

Example 1

Input
node = reverseList(buildList([1, 2, 3, 4, 5]))
Output
[5,4,3,2,1]
Five nodes, each now pointing at the one that used to point at it.

Example 2

Input
node = reverseList(buildList([7]))
Output
[7]
One node points at nothing in either direction, so it is already its own reverse.

The Code

function buildList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) {
    head = { val: values[i], next: head };
  }
  return head;
}
function toArray(node) {
  const out = [];
  while (node) {
    out.push(node.val);
    node = node.next;
  }
  return out;
}
function reverseList(head) {
  let prev = null;
  let current = head;
  while (current) {
    const nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }
  return prev;
}
toArray(reverseList(buildList([1, 2, 3, 4, 5])));
Done

The first 9 calls, of 21. This one does not fit on a page.

Step through toArray(reverseList(buildList([1, 2, 3, 4, 5]))) call by call

More like this

All linked lists examples (9) →