链表
解题思路
此题需要解决两个问题：
- 第一个问题：找到倒数第 n 个节点；
- 第二个问题：删除倒数第 n 个节点，首先拿到这个节点的前一个节点，则设置虚拟节点 dummyHead 指向 head ，找到的倒数的第 n 个节点的下一个才是要删除的节点；
初始化快慢指针指针 slow 和 fast 都指向头结点；
移动 fast 向后移动 n 个位置，此时 fast 与 show 之间相隔的元素个数为 n；
再同时相后移动 fast 与 slow ，直到 fast 走到最后，此时 slow 的下一个节点就是要删除的倒数第 n 个元素；
将 slow 的下一个节点指向下下个节点，删除倒数第 n 个元素；
复杂度
-
时间复杂度：
O(N)，其中 N 是链表的长度； -
空间复杂度：
O(1)；
代码实现
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let dmy = new ListNode(0, head);
let slow = dmy;
let fast = dmy;
// 1. fast 向后移动 n 个位置
while (n-- > 0) fast = fast.next;
// 2. fast 走到最后，slow 此时是 倒数第 n 个元素的前一个
while (fast !== null && fast.next !== null) {
fast = fast.next;
slow = slow.next;
}
// 3. slow 的下一个节点就是要删除的节点
slow.next = slow.next.next;
return dmy.next;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 147. 对链表进行插入排序
上一篇
评论
