Remove the nth node from the end

Medium TimeO(n) SpaceO(1)

Given the head of a linked list and a number n, remove the nth node counting from the end and return the head — taking the 2nd-from-last out of [1, 2, 3, 4, 5] leaves [1, 2, 3, 5]. n counts from 1, so n = 1 is the last node; n is never larger than the list, and removing the head is allowed and changes what comes back.

Examples

Example 1

Input
node = removeNthFromEnd(buildList([1, 2, 3, 4, 5]), 2)
Output
[1,2,3,5]
The 2nd from the end is the 4, and taking it out leaves the other four.

Example 2

Input
node = removeNthFromEnd(buildList([1, 2, 3, 4, 5]), 5)
Output
[2,3,4,5]
Five from the end of five nodes is the head itself, so the list now starts at 2.

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 removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let lead = dummy;
  let trail = dummy;
  for (let i = 0; i < n; i++) {
    lead = lead.next;
  }
  while (lead.next) {
    lead = lead.next;
    trail = trail.next;
  }
  trail.next = trail.next.next;
  return dummy.next;
}
toArray(removeNthFromEnd(buildList([1, 2, 3, 4, 5]), 2));
Step through toArray(removeNthFromEnd(buildList([1, 2, 3, 4, 5]), 2)) call by call

More like this

All linked lists examples (9) →