日拱算法： 删除链表的倒数第 N 个结点
「这是我参与2022首次更文挑战的第7天，活动详情查看：2022首次更文挑战」
日拱算法，功不唐捐。
平常基本上没有用过链表数据结构，链表的优势在于插入的时间复杂度良好 O(1)。
闲言少叙，冲就完事儿！
题：给一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
image.png
比如：
输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]
输入： head = [1], n = 1
输出： []
输入： head = [1,2], n = 1
输出： [1]- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
题解：
假如我们定义链表长度为l，则倒数第 n 项，正数第 l-n+1 项，其前一项为第 l-n 项；
- 双指针法解法
让前后指针 forward 和 backward 相差为 n 后同时向后推进，则当 forward 到达终点，即 forward.next 为 null 时，backward 恰好到达倒数第 n 项的前一项，连接倒数第 n 项的前后项；
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(0, head)
let forward = dummy, backward = dummy
while (n--) {
forward = forward.next
}
while (forward.next) {
forward = forward.next
backward = backward.next
}
backward.next = backward.next.next
return dummy.next
};提交通过。
image.png
除了双指针，还有简单暴力的把链表转换成数组处理：
- 数组法
将链表转换为纯数组，数组内存放链表的值，删除倒数第n个数，再将数组转换为链表；
var removeNthFromEnd = function(head, n) {
let newArr = []
let dummy = new ListNode()
let newList = dummy
while(head){
newArr.push(head.val)
head = head.next
}
newArr.splice(newArr.length - n, 1)
for(let i = 0; i < newArr.length ;i++){
newList.next = new ListNode(newArr[i]);
newList = newList.next;
}
return dummy.next
};拓展：还可以将链表节点依次存入数组stack栈，再将栈的后n个元素弹出，暴露出链表倒数第n个数的前一个节点，将其与倒数第n个数的后一个节点相连：
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(0, head)
const stack = new Array()
let pushList = dummy
while (pushList != null) {
stack.push(pushList)
pushList = pushList.next
}
for (let i = 0; i < n; i++) {
stack.pop()
}
let peek = stack[stack.length - 1]
peek.next = peek.next.next
return dummy.next
};链表的关键在于判断下一节点的指向，链表和数组也可以互相转换，但是显得会有些生硬，双向指针是更灵活的做法。
我是掘金安东尼，输出暴露输入，技术洞见生活，再会~
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
