💬 Discord
Sign In
NeetCode #321LC-19MediumLinked ListBlind 75NC 150NC 250
← Back to All Problems

#321 · #19 · Remove Nth Node From End of List(删除链表的倒数第 N 个结点)

📌 Problem Statement & Constraints

Given the head of a linked list, remove the n-th node from the end and return the head. Constraints: the number of nodes is in [1, 30], 1 <= n <= size. The follow-up asks for a single pass.

💡 Core Algorithmic Approaches

  1. Use a dummy head so removing the first node needs no special case.
  2. Advance a fast pointer n + 1 steps ahead of a slow pointer, so the gap is n + 1 nodes.
  3. Then move both until fast reaches None; slow now points at the node before the one to delete.
  4. One pass, O(1) extra space.

💻 Benchmark Python3 Implementation

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n + 1):          # gap of n+1 so slow lands before the target
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next      # unlink the target
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L): one pass over the list.
💾 Space Complexity
O(1): two pointers plus a dummy node.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing the fast pointer only n steps: then slow would land on the target rather than before it, and you could not unlink it.
  • Omitting the dummy head: removing the head (when n == size) would need a separate branch.
  • Returning head: with a dummy head, the correct return is dummy.next.
  • Counting the length first and then removing: two passes, which the follow-up forbids.