链表操作：删除倒数第N个节点

"删除链表的倒数第 N 个结点" 这道题目是关于链表操作的一个经典问题，目标是删除链表中的倒数第 N 个节点，并返回更新后的链表头节点。这个问题主要考察了链表的遍历、计数以及指针操作等技能，通常出现在算法面试或编程竞赛中。 首先，我们需要理解链表的基本概念。链表是一种数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在本题中，我们需要删除链表的倒数第 N 个节点，即从链表尾部向前数的第 N 个节点。 解题策略通常有两种方法： 1. 双指针法： - 首先，我们可以创建两个指针 `p1` 和 `p2`，初始化时都指向链表头。 - 然后，移动 `p1` 指针 N 次，使其到达倒数第 N 个节点的前一个位置。 - 接下来，同步移动 `p1` 和 `p2`，直到 `p1` 达到链表尾部。 - 这时，`p2` 指针就指向了需要删除的节点，我们将其前一个节点的 `next` 指针指向 `p2` 的下一个节点，完成删除操作。 2. 前置节点法（题目中给出的参考答案）： - 创建一个虚拟头节点 `dummy`，使得操作更加方便，`dummy` 的 `next` 指向原始链表的头节点 `head`。 - 计算链表的总长度 `length`。 - 使用一个指针 `cur` 初始化为 `dummy`，并遍历链表直到 `i < length - n + 1`，每次 `i` 增加 1，`cur` 移动到下一个节点。 - 当遍历结束时，`cur` 就会指向需要删除的节点的前一个节点。 - 更新 `cur->next` 为 `cur->next->next`，跳过需要删除的节点。 - 最后，返回 `dummy->next` 作为新的链表头节点，记得释放 `dummy`。 这个题目要求使用一趟扫描实现，也就是在一次遍历链表的过程中完成删除操作，两种方法都能满足这一要求。双指针法需要两次遍历（一次计算 N，一次同步移动），而前置节点法只需要一次遍历。题目中的 C++ 代码使用了前置节点法，它先计算链表长度，然后根据长度找到目标节点并进行删除。 注意，题目对输入的限制是链表节点数 `sz` 在 1 到 30 之间，且节点值在 0 到 100 之间，同时要求删除的节点数 `n` 也在合法范围内。因此，所给的解法在这些条件下都是有效的。在实际编程中，要确保处理边界条件，如当 `n` 大于链表长度时，应该删除链表的最后一个节点。