网站建设的7种流程,网站空白模板下载,广西seo经理,网站搜索引擎优化公司给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a;
输入#xff1a;head [1], n 1
输出#xff1a;[]示例 3#xff1a…给你一个链表删除链表的倒数第 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 步之后前后指针共同移动直到前面的指针到尾部为止首先设立预先指针 pre预先指针是一个小技巧在第 2 题中进行了讲解设预先指针 pre 的下一个节点指向 head设前指针为 start后指针为 end二者都等于 prestart 先向前移动n步之后 start 和 end 共同向前移动此时二者的距离为 n当 start 到尾部时end 的位置恰好为倒数第 n 个节点因为要删除该节点所以要移动到该节点的前一个才能删除所以循环结束条件为 start.next ! null删除后返回 pre.next为什么不直接返回 head 呢因为 head 有可能是被删掉的点时间复杂度O(n)O(n)O(n)作者画手大鹏
链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solutions/7803/hua-jie-suan-fa-19-shan-chu-lian-biao-de-dao-shu-d/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode * pre new ListNode(0,head);ListNode * start pre;ListNode * end pre;while(n!0){start start-next;n--;}while(start-next!nullptr){start start-next;end end-next;}end-next end-next-next;return pre-next;}
};
