Remove Nth Node From End of List

The problem

You are given head, the first node of a linked list, and a number n. Number the nodes from the end: the last node is 1, the one before it is 2, and so on. Remove node number n and return the first node of the list that is left. n is at least 1 and never more than the number of nodes. If the list had a single node, nothing is left, so return null. A node holds a value, val, and a link, next, to the node after it, and the last node's next is null.

What to write

type ListNode = {val:number;next:ListNode|null};

function solve(head: ListNode | null, n: number): ListNode | null

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}
n = 2

Output
{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":5,"next":null}}}}

Input
head = {"val":1,"next":null}
n = 1

Output
null

Constraints

Nodes use {val, next}; 1 ≤ n ≤ list length.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You cannot count from the end directly: a node only links forward, and nobody tells you how long the list is. Notice also that n can equal the length, and then the node to remove is the first one.

2. Hint 2: Ask a smaller question

   In 1 → 2 → 3 → 4 → 5 with n = 2 you must remove the node 4. To remove a node you change the link of a different node. Which one? How many nodes is that node behind the last node?

3. Hint 3: Name the pattern

   The node before the one to remove is n nodes behind the last node. So use two markers, variables that each point at a node: give one a head start of n nodes, then move both together. When the leader is on the last node, the follower is where you need it. This is the fast and slow pointers pattern. Read the lesson on fast and slow pointers.

4. Hint 4: State the invariant

   After the head start, the leading marker is exactly n nodes ahead of the trailing one, and it stays that way because both move one node at a time. So when the leader is on the last node, the follower is on the node before the one to remove.

5. Hint 5: Sketch the pseudocode

   Put a placeholder node in front of head and start two markers on it. Move the leading marker n nodes forward. Then move both markers one node at a time until the leading one has no node after it. Change the link of the trailing marker's node so that it skips the next node. Return the node after the placeholder.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Use a dummy head and two pointers separated by n nodes. The trailing pointer stops just before the node to remove.

The slow way

Walk the whole list to count its nodes. With L nodes, the one to remove is number L - n + 1 from the front, so walk again to the node before it and skip one node. It is correct, but it reads the list twice and needs a separate case when the first node is removed.

The insight

You can measure a distance from the end without knowing the length. Keep two markers, each a variable that points at one node, n nodes apart and move them together. When the leading marker reaches the last node, the trailing one is n nodes behind it: the node before the one to remove.

Step by step

1. Put a placeholder node in front of the first node. A placeholder, often called a dummy node, is an extra node with no real value. With a placeholder, every real node has a node in front of it, so the first node is removed the same way as any other.
2. Both markers start on the placeholder; one moves n nodes ahead. After this head start the leading marker is n nodes ahead of the trailing one. From here on they move together, so that distance never changes.
3. Move both markers until the leading one is on the last node. The last node is number 1 from the end. The trailing marker is n nodes further back, which is the node before number n from the end.
4. The trailing marker is before the node to remove: skip that node. A node is removed by changing the link of the node before it. That link now points one node further, so the removed node can no longer be reached from the head.
5. Return the list that starts after the placeholder. The placeholder's link is the first node of the result: the old first node, or the second node if the first was removed, or null if the only node was removed.

The same numbered steps are the comments in each solution.

function solve(head, n) {
  // 1. Put a placeholder node in front of the first node
  const dummy = { val: 0, next: head };
  // 2. Both markers start on the placeholder; one moves n nodes ahead
  let fast = dummy,
    slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next;
  // 3. Move both markers until the leading one is on the last node
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  // 4. The trailing marker is before the node to remove: skip that node
  slow.next = slow.next.next;
  // 5. Return the list that starts after the placeholder
  return dummy.next;
}

type ListNode = { val: number; next: ListNode | null };
function solve(head: ListNode | null, n: number): ListNode | null {
  // 1. Put a placeholder node in front of the first node
  const dummy: ListNode = { val: 0, next: head };
  // 2. Both markers start on the placeholder; one moves n nodes ahead
  let fast: ListNode | null = dummy,
    slow = dummy;
  for (let i = 0; i < n; i++) fast = fast!.next;
  // 3. Move both markers until the leading one is on the last node
  while (fast!.next) {
    fast = fast!.next;
    slow = slow.next!;
  }
  // 4. The trailing marker is before the node to remove: skip that node
  slow.next = slow.next!.next;
  // 5. Return the list that starts after the placeholder
  return dummy.next;
}

def solve(head, n):
    # 1. Put a placeholder node in front of the first node
    dummy = ListNode(0, head)
    # 2. Both markers start on the placeholder; one moves n nodes ahead
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    # 3. Move both markers until the leading one is on the last node
    while fast.next:
        fast = fast.next
        slow = slow.next
    # 4. The trailing marker is before the node to remove: skip that node
    slow.next = slow.next.next
    # 5. Return the list that starts after the placeholder
    return dummy.next

Example 1, traced

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}
n = 2

Output
{"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":5,"next":null}}}}

Why it works

After the head start the leading marker is n nodes ahead, and moving both together keeps it there. So when the leading marker is on the last node, the trailing one is on the node before the one to remove. The placeholder makes this true even when the node to remove is the first.

Time and space

Time O(n), extra space O(1). The leading marker goes from the placeholder to the last node, and the trailing marker follows, so the list is read in one pass: O(n) time. Here n is the number of nodes, not the parameter n. The placeholder and the two markers are all the extra memory: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Start both markers on a placeholder, not on the first node. Otherwise the leading marker runs off the end of the list whenever the first node is the one to remove, and reading the link of null is an error.
• Stop when the leading marker is on the last node, not past it. One move too many puts the trailing marker on the node to remove, so the node after it goes instead: in example 1, 5 instead of 4.
• Return the node after the placeholder, not head. When the first node is removed, head still points at it and it still links to the rest, so the list comes back unchanged.

Pattern

Fast and slow pointers. Builds on Merge Two Sorted Lists and Reorder List.

Keep going