19. 删除链表的倒数第 N 个结点
题目描述
输入链表的头节点 head 和整数 n，链表用数组表示，如 [1,2,3]。
删掉从链表末尾往前数的第 n 个节点，返回删除后链表的头节点。如果删除后链表为空，返回 null（即空链表）。
示例 1
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
解释：倒数第 2 个节点是 4，删去后剩 [1,2,3,5]。
示例 2
输入：head = [1], n = 1 输出：[]
解释：删掉唯一的节点后链表为空。
示例 3
输入：head = [1,2], n = 1 输出：[1]
解释：倒数第 1 个是尾节点 2，删去后剩 [1]。
数据范围
- 链表节点数记为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：能否只遍历链表一次就完成删除？
解题思路：快慢双指针（一次遍历）
快慢指针从哑节点开始，快指针先走 n 步，再同步走至 fast 为尾节点。
为什么正确
同步移动阶段 fast 比 slow 超前 n 个节点，因此 slow 最终在待删除节点之前。
复杂度分析
时间 O(n)，额外空间 O(1)，这里 n 表示链表长度。
易错点
需要哑节点来统一处理删除头节点的情况。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeNthFromEnd(self, head, n):
dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.nextclass Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.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* slow = dummy;
ListNode* fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
while (fast->next) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{0, head}
slow, fast := dummy, dummy
for i := 0; i < n; i++ {
fast = fast.Next
}
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(0, head);
let slow = dummy, fast = dummy;
for (let i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
};function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow: ListNode = dummy, fast: ListNode = dummy;
for (let i = 0; i < n; i++) {
fast = fast.next!;
}
while (fast.next) {
slow = slow.next!;
fast = fast.next;
}
slow.next = slow.next!.next;
return dummy.next;
};其他解法
两者都是线性时间、常数空间。两次遍历先显式算长度，双指针用固定间距隐式定位。
解法 2：先求长度再定位（两次遍历） 时间 O(L)，空间 O(1)
第一次遍历统计链表长度 L，倒数第 n 个节点就是正数第 L-n+1 个。从哑节点出发走 L-n 步到达它的前驱，把前驱的 next 指向下下个节点。
最直观的做法，把「倒数」转换成「正数」。复杂度与双指针相同，但要遍历两趟；双指针通过让快指针领先 n 步省去了求长度那趟。
class Solution:
def removeNthFromEnd(self, head, n):
length = 0
cur = head
while cur:
length += 1
cur = cur.next
dummy = ListNode(0, head)
prev = dummy
for _ in range(length - n):
prev = prev.next
prev.next = prev.next.next
return dummy.nextclass Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) length++;
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
for (int i = 0; i < length - n; i++) prev = prev.next;
prev.next = prev.next.next;
return dummy.next;
}
}class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int length = 0;
for (ListNode* cur = head; cur; cur = cur->next) length++;
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
for (int i = 0; i < length - n; i++) prev = prev->next;
prev->next = prev->next->next;
return dummy->next;
}
};func removeNthFromEnd(head *ListNode, n int) *ListNode {
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
dummy := &ListNode{0, head}
prev := dummy
for i := 0; i < length-n; i++ {
prev = prev.Next
}
prev.Next = prev.Next.Next
return dummy.Next
}var removeNthFromEnd = function(head, n) {
let length = 0;
for (let cur = head; cur; cur = cur.next) length++;
const dummy = new ListNode(0, head);
let prev = dummy;
for (let i = 0; i < length - n; i++) prev = prev.next;
prev.next = prev.next.next;
return dummy.next;
};function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let length = 0;
for (let cur = head; cur; cur = cur.next) length++;
const dummy = new ListNode(0, head);
let prev: ListNode = dummy;
for (let i = 0; i < length - n; i++) prev = prev.next!;
prev.next = prev.next!.next;
return dummy.next;
}