lc019

19.删除链表的倒数第 N 个结点

1. 题目描述

给你一个链表，删除链表的倒数第 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.两次遍历链表，第一次遍历得到链表的长度len，当遍历到第len−n+1 个节点时，就是我们需要删除的节点。 2.采用双指针遍历，先让快指针走n步，再让慢指针和快指针一起遍历，直到快指针遍历到链表最后一个结点，此时慢指针所指的位置即要删除的结点。