开网站是干什么的,重庆建设行业信息网站,网站建设2018需要什么,sketchup模型库免费下载删除链表的倒数第N个结点 题目要求题目示例解题思路从题目中的已知出发思考寻找目标结点条件转换核心思路 需要注意的点改进建议 完整代码提交结果 题目要求
给你一个链表#xff0c;删除链表的倒数第n个结点#xff0c;并且返回链表的头结点。
题目示例
示例 1#xff1… 删除链表的倒数第N个结点 题目要求题目示例解题思路从题目中的已知出发思考寻找目标结点条件转换核心思路 需要注意的点改进建议 完整代码提交结果 题目要求
给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。
题目示例
示例 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值来定位到我们的目标结点
从题目中的已知出发思考
寻找目标结点
我们可以设想用两个指针来寻找目标结点假设链表长度一共为lenth倒数第n个就是正数第lenth-n1个那么也就是说需要一个指向头结点的指针从头结点开始走lenth-n步就走到了需要删除的那个结点。
条件转换
上述的寻找思路我们发现需要遍历两次链表才能实现但是在要求遍历一次时我们就可以想到“快慢指针”双指针
核心思路
定义一个快指针和一个慢指针都先指向头结点然后快指针先走n步然后快、慢指针同时走发现当快指针走到链表结尾的时候慢指针就刚好走到了要删除结点的前一个结点那么此时只需要将慢指针的next指向慢指针next的next即可完成删除操作就本题来说可以忽略释放删除结点这个操作当然释放一下也可以
需要注意的点
如果采用上面的思路操作的话那么就会发现示例二是不能通过的因为会出现野指针的问题。
改进建议
创建一个前驱结点快、慢指针都从前驱结点开始遍历这样就可以成功的删除头结点并返回NULL了。
完整代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* prehead new ListNode(0);prehead-next head;ListNode* slow prehead;ListNode* fast prehead;while(n--){fast fast-next;}while(fast-next!nullptr){fast fast-next;slow slow-next;}slow-next slow-next-next;return prehead-next;}
};提交结果
