题目
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
链表类
答题处
规则示例
规则
1.链表中结点的数目为 sz
2.1 <= sz <= 30
3.0 <= Node.val <= 100
4.1 <= n <= sz
示例1
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例2
输入:head = [1], n = 1
输出:[]
示例3
输入:head = [1,2], n = 1
输出:[1]
解题分析一:栈
我们可以一开始就遍历链表,边遍历边放入一个栈容器当中,栈的特点是先进后出,那么之后我们再遍历n次进行弹栈操作,把倒数n个节点都从栈中弹出,那么这时在栈顶的节点,便是倒数第n个节点的前一个节点,我们只需要让该节点指向它的下一个的下一个节点即可以删除倒数第n个节点。
需要注意的就是,为了考虑特殊情况,比如移除的对象是头节点 ,我们可以在头部加入一个节点,方便我们进行 取栈顶 和 next = next.next 操作
我们以 head = [1,2,3,4,5], n = 2 为例
之后只需要返回 head.next 就可以得到真正的新链表的头结点了
之所以加入一个新的head,是因为
考虑当移除倒数第n个节点是头结点
比如:链表中只有1个元素,移除倒数第1个节点
我们添加的head始终是不会被移除的,最后我们只需要返回head.next,不用操心改变了真正的头结点引用的问题。
解题一:栈
解题分析二:快慢指针
所谓快慢指针就是指:
一个走的快的指针或者走在前面的指针
一个走的慢的指针或者走在后面的指针
如果我们让快指针提前走 n 步(这个n就是函数传入的要删除的倒数n个节点的n)
而此时我们再让慢指针和快指针一起一步一步的走,那么当快指针走到尾部时停止
为了考虑移除的是头结点,所以我们需要在头结点前面加一个自定义头结点,那么在加入了一个新的头结点的前提下,这时停下来,慢指针刚好就是倒数第n个节点的前一个节点了
我们以 head = [1,2,3,4,5], n = 2 为例
解题二:快慢指针
总结
本题还不止这两种解法,你还可以思考更多的解法留言在评论区哦
END