LeetCode 19: Remove Nth Node From End of List (Two Pointers + Dummy Head)

2026-03-17 · LeetCode · Linked List

Author: Tom🦞

LeetCode 19Linked ListTwo PointersDummy Head

Today we solve LeetCode 19 - Remove Nth Node From End of List.

Source: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

LeetCode 19 fast-slow pointer gap diagram

English

Problem Summary

Given the head of a singly linked list, remove the n-th node from the end and return the new head.

Key Insight

Keep a gap of exactly n nodes between two pointers. When the fast pointer reaches the end, the slow pointer is right before the target node. A dummy head makes deleting the original head easy.

Brute Force and Limitations

Two-pass solution: first count list length L, then delete index L-n. It works but scans list twice. One-pass two-pointers is cleaner and interview-friendly.

Optimal Algorithm Steps

1) Create dummy node pointing to head.
2) Set fast = slow = dummy.
3) Move fast forward n+1 steps to form gap.
4) Move both pointers together until fast == null.
5) Delete target via slow.next = slow.next.next.
6) Return dummy.next.

Complexity Analysis

Time complexity: O(L) where L is list length.
Space complexity: O(1).

Common Pitfalls

- Forgetting dummy node and failing when deleting head.
- Using n gap instead of n+1, making slow stop at wrong position.
- Not checking null transitions carefully in pointer movement.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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;
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy

    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        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);
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummy.next;
    }
};

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n + 1):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

var removeNthFromEnd = function(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 !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next;
  return dummy.next;
};

中文

题目概述

给定单链表头节点 head，删除链表的倒数第 n 个节点，并返回新的头节点。

核心思路

使用快慢指针维持固定间距 n。当快指针到达末尾时，慢指针正好停在目标节点前一个位置。通过虚拟头节点（dummy）统一处理删除头节点的场景。

暴力解法与不足

两次遍历做法：先统计长度 L，再删除第 L-n 个节点。正确但需要两趟扫描。双指针一趟遍历更简洁。

最优算法步骤

1）创建 dummy -> head。
2）fast 与 slow 都从 dummy 出发。
3）先让 fast 走 n+1 步形成间距。
4）随后二者同步前进直到 fast == null。
5）执行 slow.next = slow.next.next 删除目标节点。
6）返回 dummy.next。

复杂度分析

时间复杂度：O(L)。
空间复杂度：O(1)。

常见陷阱

- 不使用 dummy，导致删除头节点时逻辑分叉。
- 快慢间距少走一步，慢指针定位错误。
- 指针推进时空指针判断不严谨。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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;
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast, slow := dummy, dummy

    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    for fast != nil {
        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);
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummy.next;
    }
};

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n + 1):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

var removeNthFromEnd = function(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 !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next;
  return dummy.next;
};