19. 删除链表的倒数第 N 个结点
一句话套路快指针先走 n 步,再同步走到尾部
题目描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1 输出:[]
示例 3:
输入:head = [1,2], n = 1 输出:[1]
提示:
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶:你能尝试使用一趟扫描实现吗?
思路
时间
O(n)空间
O(1)思路
fast 先走 n 步,然后两人同速前进;fast 到末尾时 slow 正好停在待删点前驱。
有哨兵才能统一处理「删头结点」(倒数第 n 个正好是 head)。
图解
链表结构(来自本仓库测试数据)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0019 {
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* fast = &dummy;
for (int i = 0; i < n; ++i) fast = fast->next; // 先走 n 步
ListNode* slow = &dummy;
while (fast->next) {
slow = slow->next;
fast = fast->next;
}
ListNode* victim = slow->next;
slow->next = victim->next;
delete victim; // 题目语义是删除,测试里就不能让它泄漏
return dummy.next;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0019::Solution s;
ListNode* a = buildList({1, 2, 3, 4, 5});
CHECK_EQ(listToVec(s.removeNthFromEnd(a, 2)), vector<int>{1, 2, 3, 5});
ListNode* b = buildList({1});
CHECK_TRUE(s.removeNthFromEnd(b, 1) == nullptr); // 删到空
ListNode* c = buildList({1, 2});
CHECK_EQ(listToVec(s.removeNthFromEnd(c, 2)), vector<int>{2}); // 删头