焦茶/夏コミ本に収録です 小宇宙
680 字
3 分钟
删除链表的倒数第 N 个结点
上一篇 奇偶排序数组 用到了双指针的思想，这是一道使用快慢指针实现一次遍历链表删除倒数第 n 个结点，比较经典的链表算法题，算是对双指针的扩展运用，在 LeetCode 中等难度 19. 删除链表的倒数第 N 个结点 ，如果没有一次遍历的限制，题目本身很简单，感觉官方有点为了用方法而出的限制
题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例
输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]思路
只遍历一次链表，只能从正数去确定第几个结点是倒数第 n 个结点，并且要遍历到最后一个结点才能确定，一个指针肯定是行不通的，很容易联想到使用双指针去解决，最终状态是当快指针遍历完，慢指针刚好到倒数第 n 个结点
我们先尝试找出正数和倒数的关系，把问题化简为：已知链表长度 len，倒数第 n 个结点，求正数第 k 个结点
代入具体数字，多尝试寻找规律
链表长度为5，倒数第2个结点，正数是第4个结点链表长度为5，倒数第1个结点，正数是第5个结点链表长度为5，倒数第5个结点，正数是第1个结点...可以看出存在一个规律，k = len - n + 1
而 len 可以看作是快指针刚好遍历完，k 可以看作是慢指针刚好走到倒数第 n 个结点，为了方便删除倒数第 n 个结点，慢指针应该走到倒数第 n + 1 个结点，所以我们得到
k = len - (n + 1) + 1，即 k = len - n
继续思考，快指针肯定是要遍历完的，那慢指针什么时候才开始移动？
等同于使公式 k >= 0，必须满足 len >= n，意味着快指针走到 n 时，慢指针才开始移动
public ListNode removeNthFromEnd(ListNode head, int n) { // 因为链表的头结点已经是1个，指针需要指向一个虚拟的0个结点 ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; // 记录快指针移动的长度 int len = 0; // 快指针遍历链表 while (fast.next != null) { // 慢指针开始移动 if (len >= n) { slow = slow.next; } fast = fast.next; len++; } // 删除倒数第 n 个结点 slow.next = slow.next.next; // 返回原链表 return dummy.next;}