网站建设网络,欧美教育网站模板,seo经理招聘,网站建设培训哪家好代码随想录二刷 #xff5c; 链表 #xff5c; 删除链表的倒数第N个节点 题目描述解题思路 代码实现双指针法 题目描述
19.删除链表的倒数第N个节点
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a;
输入… 代码随想录二刷 链表 删除链表的倒数第N个节点 题目描述解题思路 代码实现双指针法 题目描述
19.删除链表的倒数第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]
提示
链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz
进阶你能尝试使用一趟扫描实现吗
解题思路 代码实现
双指针法
设置两个指针fast和slowfast指针先移动 n 步然后fast指针和slow指针同时移动直到fast指针指向链表末尾最后删掉slow指向的元素即可。
class Solution{
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead new ListNode(0);dummyHead - next head;ListNode* slow dummyHead;ListNode* fast dummyHead;// fast指针移动 n 步while (n-- fast ! NULL){fast fast - next;}// fast指针再移动一步因为设置了虚拟头节点fast fast - next;// fast 、slow同时移动fast移动到末尾时slow移动到了倒数第 n 个位置while (fast ! NULL) {fast fast - next;slow slow - next;}// 删除slow指向的元素slow - next slow - next - next;// 返回头节点return dummyHead - next;}
};
