HHot 100C++ 图解

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 <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

 

进阶:你能尝试使用一趟扫描实现吗?

思路

时间O(n)
空间O(1)

思路

fast 先走 n 步,然后两人同速前进;fast 到末尾时 slow 正好停在待删点前驱。

有哨兵才能统一处理「删头结点」(倒数第 n 个正好是 head)。

图解

1 i0 2 i1 3 i2 4 i3 5 i4
链表结构(来自本仓库测试数据)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/07_linked_list.cpp20 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q19_remove_nth_from_end7 行
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});  // 删头

↑↓ 选择↵ 打开/ 随时唤起