leetcode19:删除链表倒数第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
进阶：你能尝试使用一趟扫描实现吗？
步骤 1：问题分析
问题性质：
- 给定一个单链表，需要删除倒数第
n个节点，并返回链表的头节点。 - 删除操作需要在链表中进行节点的连接调整。
输入输出条件：
- 输入：链表的头节点
head和一个整数n（表示倒数第n个节点）。 - 输出：删除指定节点后的链表头节点。
限制：
- 链表节点数
sz在[1, 30]范围内。 0 <= Node.val <= 1001 <= n <= sz
边界条件：
n == 1且sz == 1：链表仅有一个节点，删除后链表为空。n == sz：删除第一个节点，调整头节点即可。1 < n < sz：删除链表中间节点，需重新调整连接。
步骤 2：解题思路
由于要求一次遍历删除倒数第 n 个节点，使用双指针法（或称“快慢指针”）是一个有效的方法。
算法设计思路：
-
创建虚拟头节点：
- 使用一个虚拟节点
dummy指向head，简化删除操作的边界情况，例如删除第一个节点时可以避免特殊处理。
- 使用一个虚拟节点
-
初始化双指针：
- 初始化两个指针
first和second都指向dummy。
- 初始化两个指针
-
移动
first指针：- 将
first指针向前移动n + 1步，使first与second之间有n个节点的距离。
- 将
-
移动
first和second指针：- 同时移动
first和second，直到first到达链表末尾。 - 此时
second指向倒数第n + 1个节点（即要删除节点的前一个节点）。
- 同时移动
-
删除节点：
- 调整
second->next指向second->next->next，跳过目标节点，完成删除。
- 调整
-
返回结果：
- 返回
dummy->next，即删除指定节点后的链表头。
- 返回
复杂度分析：
- 时间复杂度：O(sz)，仅需一次遍历。
- 空间复杂度：O(1)，使用常量级别的辅助指针。
步骤 3：C++代码实现
代码详解
-
初始化虚拟节点：
- 使用
dummy节点指向head，处理边界情况（如删除头节点）。
- 使用
-
前进
first指针：first指针前进n + 1步，这样first和second间隔n个节点。
-
双指针同步前进：
- 当
first到达链表末尾时，second位于要删除节点的前一个节点。
- 当
-
删除节点：
- 调整
second->next，跳过目标节点，完成删除。
- 调整
-
返回结果：
dummy->next即为新链表的头节点。
步骤 4：启发与算法优化
-
双指针法的灵活性：双指针法在链表操作中非常高效，尤其是在找倒数节点、判断环、合并链表等场景中可以实现一趟扫描。这种方法不仅节省时间，还避免了不必要的空间浪费。
-
虚拟节点的优势：虚拟头节点
dummy是链表题中的常用技巧，通过dummy可以简化删除头节点的处理，无需特意判断头节点的删除情况。 -
算法优化：通过一次遍历解决倒数问题，比传统的两次遍历（先计算链表长度，再定位删除节点）更高效，避免了不必要的额外计算。
步骤 5：实际应用及场景分析
应用场景： 删除链表的倒数节点的算法可以应用在日志系统、队列管理系统、缓存控制等需要删除最近使用的数据场景。例如：
- 缓存数据管理：在缓存数据中，可以通过链表来维护最近最少使用的数据记录。如果某些数据长期未被访问且缓存超出容量，可以删除最不常用的数据（即倒数位置的数据）。
应用示例： 在一项日志管理系统中，需要按顺序记录用户的行为记录。系统可使用链表存储日志记录，保持其顺序。如果系统检测到日志条目数超出限制，可以删除倒数的第 n 条日志记录以优化存储空间。
原文地址：https://blog.csdn.net/D2510466299/article/details/143650054
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！