38. Remove Nth Node From End of List

MediumLinked ListsAlso on LeetCode ↗

Remove the n-th node from the end of the list and return the head. Try to do it in one pass.

Example 1

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

Example 2

Input: head = [1], n = 1

Output: []

Hint 1

Move a fast pointer n+1 steps ahead, then move both until fast falls off the end.

Hint 2

A dummy node handles deleting the head.

Linked ListTwo Pointers

Reference solution for One pass with a gap (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n + 1):        # open a gap of n nodes
            fast = fast.next
        while fast:
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next    # slow is just before the node to delete
        return dummy.next

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
        for (int i = 0; i <= n; i++) fast = fast.next;   // gap of n nodes
        while (fast != null) { 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(0, head), *fast = &dummy, *slow = &dummy;
        for (int i = 0; i <= n; i++) fast = fast->next;  // gap of n nodes
        while (fast) { fast = fast->next; slow = slow->next; }
        slow->next = slow->next->next;
        return dummy.next;
    }
};

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

38. Remove Nth Node From End of List

Example 1

Example 2

Approach 1: Two passes

Approach 2: One pass with a gap ✅