链表

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

中等#19Java时间 O(n)空间 O(1)

题目要做什么

删除链表倒数第 n 个节点并返回头节点。n 必须在 1 到链表长度之间。

题目示例输入head = [1,2,3,4,5], n = 2
题目示例输出[1,2,3,5]

01 为什么这样做

哑节点可以统一删除头节点的情况。fast 先比 slow 多走 n 步,之后一起前进;fast 到尾节点时,slow 位于待删除节点之前。

始终成立的条件

同步移动阶段,fast 与 slow 相隔 n 个 next 连接。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode removeNthFromEnd(ListNode head, int n) {3        ListNode dummy = new ListNode(0, head);4        ListNode slow = dummy, fast = dummy;5        for (int i = 0; i < n; i++) fast = fast.next;6        while (fast.next != null) {7            slow = slow.next;8            fast = fast.next;9        }10        slow.next = slow.next.next;11        return dummy.next;12    }13}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索