19. 删除链表的倒数第 N 个结点
3 min
题目
解法：双指针
思路
核心思想是使用双指针保持固定间隔移动。第一段：通过快慢指针制造n+1的间隔，使慢指针最终指向目标节点的前驱。第二段：当快指针移动n步后，两指针同步移动直至快指针到达末尾，此时慢指针正好位于倒数第n+1个节点，该位置可直接操作删除目标节点。第三段：
- Step 1: 创建虚拟头结点简化边界处理
- Step 2: 快指针先移动n步建立间隔
- Step 3: 双指针同步移动直至快指针到达末尾
- Step 4: 通过慢指针跳过目标节点完成删除
复杂度
- 时间复杂度: ，其中L为链表长度。仅需一次完整遍历，快指针的移动是主要耗时操作
- 空间复杂度: ，仅使用常数级别的额外空间存储指针和虚拟节点
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* fast = dummy;
ListNode* slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* fast = dummy;
ListNode* slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode* toDelete = slow->next;
slow->next = slow->next->next;
delete toDelete;
ListNode* newHead = dummy->next;
delete dummy;
return newHead;
}
};