TNotes.leetcode

Appearance

to top

0019. 删除链表的倒数第 N 个结点【中等】 ​

  • 本文的题解中提到了一个概念【哑节点（dummy node）、哨兵节点（sentinel node）】这个东西在处理链表中还是蛮常用的，如果不清楚什么是【哑节点（dummy node）、哨兵节点（sentinel node）】，可以结合这道题来了解一下。

1. 📝 Description ​

leetcode

给你一个链表，删除链表的倒数第 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

进阶： 你能尝试使用一趟扫描实现吗？

2. 💻 题解.1 - 三指针暴力解法 ​

javascript
var removeNthFromEnd = function (head, n) {
  let p1 = p2 = p3 = new ListNode(-1, head), len = 0;
  while (p1 = p1.next) len++;
  let target = len - n + 1;
  // console.log('链表长度：', len, '需要删除的目标元素是第几个元素：', target);
  while (--target) p2 = p2.next;
  p2.next = p2.next.next;
  return p3.next;
};
  • 解题思路：
    • 核心步骤共两步
      • p1 负责探路，获取到链表的总长度
      • p2 负责找到需要被删除的那一个成员，然后将其从链表中剔除
  • 在获取到链表的总长度之后，结合已知的需要被删除的倒数第 n 个成员，就可以获取到需要被删除的那个成员是第几个成员；然后再正向的遍历链表，找到指定成员，并将其删除即可。
  • 问：为什么需要新增一个 p3，让 p3 指向 head（即 p3.next === head）然后最终返回 p3.next 而不是直接返回 head？p3 存在的意义是？
    • p3 的作用是作为一个哑节点（dummy node）或哨兵节点（sentinel node）。它的存在主要是为了处理一些边界情况，特别是当需要删除的节点是链表的第一个节点时。使用哑节点可以简化代码逻辑，避免对头节点进行特殊处理。
    • 下面是 p3 这个节点存在的几点意义：
      1. 处理删除头节点的情况：如果要删除的是头节点（即 target 为 1），直接操作 head 会比较麻烦，因为你需要更新 head 指针。通过引入 p3 作为哑节点，你可以统一处理所有情况，包括删除头节点。这样，即使删除了头节点，你也可以简单地返回 p3.next，而不需要额外的条件判断。
      2. 保持代码简洁：使用哑节点可以使代码更加简洁和易于理解。你不需要检查是否需要删除头节点，只需要关注如何找到目标节点并删除它。
      3. 确保链表结构完整：有了哑节点，你可以确保链表结构始终是完整的，不会因为删除操作导致链表断裂。
    • 详细执行流程描述：
      • 首先，创建一个哑节点 p3，它的 next 指向 head。
      • 然后，计算链表的长度 len。
      • 计算出需要删除的目标节点的位置 target。
      • 使用 p2 来遍历到目标节点的前一个节点。
      • 将 p2.next 指向 p2.next.next，从而删除目标节点。
      • 最后，返回 p3.next 作为新的头节点。
    • 这样做之后，无论删除的是哪个节点，你都可以通过 p3.next 返回正确的链表头部，而不需要考虑特殊情况。
    • 如果你不使用哑节点，那么你需要在删除头节点时单独处理这种情况，这会使代码变得更复杂且容易出错。因此，使用哑节点是一种常见且有效的方法来简化链表操作。