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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

1
2

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2

输入：head = [1], n = 1
输出：[]

示例 3：

1
2

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

思路

一般来说，链表相关的算法题考察的知识点有以下几个：

• 递归
• 反转
• 双指针
• 环

本题解题思路如下：

快慢指针

1、再原链表的前面添加一个虚拟头结点，使得原链表的头结点和其余的结点地位一样，进行删除操作时不需要进行区分处理。

2、在原链表的头部设置一个指针 former，使用 for 循环让它向后移动 n 步。

3、在原链表的头部再设置一个指针 cur，同时在虚拟头结点位置设置一个指针 latter。

4、接下来，同时让这三个指针向后移动，直到 former 指向了 null，此时 cur 指向的恰好就是倒数第 n 个结点。

5、由于 latter 一直在 cur 的上一个结点位置，这个时候只需要让 latter 指向 cur 的下一个结点，那么也就完成了删除 cur 结点的操作。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 添加表头 ListNode dummy = new ListNode(-1); dummy.next = head; // 寻找需要删除的节点节点 ListNode cur = head; // 指针 latter 指向虚拟头结点 ListNode latter = dummy; ListNode former = head; // 让 former 指针先向前走 n 步 for (int i = 0 ; i < n; i++) { // former 指针向后移动 former = former.next; } // 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL while (former != null) { // former 指针向后移动 former = former.next; // latter 来到 cur 的位置 latter = cur; // cur 指针向后移动 cur = cur.next; } // 删除 cur 这个位置的结点 latter.next = cur.next; // 返回虚拟头结点的下一个结点 return dummy.next; } }