dummy + 快慢指针相距 n+1，快指针到尾时慢指针在待删节点前一位。
OJ: leetcodecn
题目 ID: remove-nth-node-from-end-of-list
难度:普及+/提高
标签:链表双指针cpppython
日期: 2026-07-28 22:05
题意
删除链表倒数第 n 个节点，返回头节点。
思路
两次遍历版：先求长度再删除。一次遍历版：dummy + 快慢指针，快指针先走 n 步，然后两指针同步走，快指针到尾部时慢指针刚好在待删节点的前一个节点。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：dummy + 快慢指针相距 n+1，快到尾时慢在待删前一位。
#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode dummy(0);
dummy.next = head;
auto fast = &dummy, slow = &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;
}
};
ListNode *build(istream &in, int n) {
if (!n)
return nullptr;
auto head = new ListNode(0), cur = head;
for (int i = 0, v; i < n; i++) {
in >> v;
cur->next = new ListNode(v);
cur = cur->next;
}
return head->next;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len, n;
cin >> len >> n;
auto head = build(cin, len);
head = Solution().removeNthFromEnd(head, n);
for (auto p = head; p; p = p->next)
cout << p->val << ' ';
return 0;
}python
#!/usr/bin/env python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
def build(arr):
dummy = cur = ListNode(0)
for v in arr:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def main() -> None:
length, n = map(int, input().split())
a = list(map(int, input().split()))
head = build(a)
head = Solution().removeNthFromEnd(head, n)
while head:
print(head.val, end=" ")
head = head.next
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
总结
快慢指针定位倒数第 k 个元素是链表的经典技巧。dummy 节点统一处理删头节点的边界情况。