Remove Nth Node From End of List

MediumLinked List Two Pointers

A rail yard models a freight train as a singly linked list. The head is the car right behind the locomotive, and each node holds a car code and links to the next car toward the back. A damaged car must be taken out, and the inspection report identifies it by its position counted from the back: n = 1 is the last car.

Remove that car and return the head of the shortened train. n is always between 1 and the number of cars, so the car exists. Removing the only car leaves an empty train.

Example 1

Input: head = [101,205,330,412], n = 3
Output: [101,330,412]

Explanation: Counting from the back, 412 is first, 330 second and 205 third.

Example 2

Input: head = [8,6], n = 2
Output: [6]

Explanation: The car to remove is the head itself, so the second car becomes the new head.

Example 3

Input: head = [3,9,4], n = 1
Output: [3,9]

Explanation: n = 1 always removes the last car.

Constraints

The train has between 1 and 200 cars.
Each car code is an integer from -1000 to 1000.
n is between 1 and the number of cars.

💡 Hint 1

Counting the length first and then walking to position length - n works in two passes. Can you do it in one?

💡 Hint 2

Start two pointers at the same place and move one of them n steps ahead. Now move both until the leader hits the end.

💡 Hint 3

A dummy node before the head makes deleting the head no different from deleting any other node.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use two pointers with a fixed gap. Put a dummy node in front of head and start both fast and slow there. Advance fast by n + 1 steps, so exactly n nodes sit between the two pointers. Then move both one step at a time until fast falls off the end. At that moment slow is the node just before the one to delete, so slow.next = slow.next.next unlinks it. Returning dummy.next covers the case where the head itself was removed.

Time O(L), one pass over the L nodesSpace O(1)

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i <= n; i++) fast = fast.next;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
function removeNthFromEnd(head, n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit