题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
难度:Middle
前置知识
- 链表
- 双指针
公司
- 阿里
- 百度
- 腾讯
- 字节
思路
这里我们可以使用双指针算法,不妨设为指针 A 和 指针 B。指针 A 先移动 n 次, 指针 B 再开始移动。当 A 到达 null 的时候, 指针 B 的位置正好是倒数第 n。这个时候将 B 的指针指向 B 的下下个指针即可完成删除工作。
算法:
- 设置虚拟节点 dummyHead 指向 head(简化判断,使得头结点不需要特殊判断)
-
设定双指针 p 和 q,初始都指向虚拟节点 dummyHead
-
移动 q,直到 p 与 q 之间相隔的元素个数为 n
-
同时移动 p 与 q,直到 q 指向的为 NULL
-
将 p 的下一个节点指向下下个节点
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
关键点解析
- 链表这种数据结构的特点和使用
-
使用双指针
-
使用一个 dummyHead 简化操作
代码
代码支持: JS, Java
Javascript Code:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
let i = -1;
const noop = {
next: null,
};
const dummyHead = new ListNode(); // 增加一个dummyHead 简化操作
dummyHead.next = head;
let currentP1 = dummyHead;
let currentP2 = dummyHead;
while (currentP1) {
if (i === n) {
currentP2 = currentP2.next;
}
if (i !== n) {
i++;
}
currentP1 = currentP1.next;
}
currentP2.next = ((currentP2 || noop).next || noop).next;
return dummyHead.next;
};
Java Code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
TreeNode dummy = new TreeNode(0);
dummy.next = head;
TreeNode first = dummy;
TreeNode second = dummy;
if (int i=0; i<=n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
复杂度分析
– 时间复杂度:$O(N)$
– 空间复杂度:$O(1)$
– 原题leetcode链接:19.removeNthNodeFromEndofList
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com