31. Remove Nth Node From End of List

MediumLinked List Two Pointers

Given the head of a singly linked list and an integer n, delete the n-th node counting from the end (the last node is n = 1) and return the head of the resulting list.

n is always between 1 and the length of the list, so the node to delete always exists.

Example 1

Input: head = [10,20,30,40,50], n = 2
Output: [10,20,30,50]

Explanation: The second node from the end holds 40.

Example 2

Input: head = [7], n = 1
Output: []

Example 3

Input: head = [1,2], n = 2
Output: [2]

Explanation: Removing the second-from-last node of a two-node list removes the head itself.

Constraints

The number of nodes sz is in the range [1, 200]
-1000 <= Node.val <= 1000
1 <= n <= sz

💡 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