题目代码class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); //因为删除的可能是头结点所以用虚拟头结点更方便避免分类讨论 dummyHead-next head; ListNode* slow dummyHead; ListNode* fast dummyHead; while(fast!NULLn--){//防止操作空指针 fastfast-next; } fastfast-next; while(fast!NULL){ fastfast-next; slowslow-next; } slow-nextslow-next-next;//删节点操作 return dummyHead-next; } };思路快慢指针结合虚拟头结点。利用快慢指针实现对链表的遍历解决链表无法定位“倒数第N个结点”的痛点因为当快指针到达链表末尾的时候慢指针正好位于要删除的结点的前一个~我们直接一个 slow-nextslow-next-next;就可以实现删除操作啦~至于虚拟头结点的存在是为了避免链表只有一个结点的情况这样的话就不需要特殊讨论了有个dummyhead比较方便统一写代码~小结1.为啥会出现多出来的一行fastfast-next?让fast实际比slow多走n1步因为最终我们的slow其实是在被删除结点前的位置哦~2. while(fast!NULLn--)指的是 fast 不为空且n03.快慢指针一般用于什么时候✅️链表不知道长度要找倒数 / 中间位置本题就是显而易见啊✅️判断链表有没有环这个有印象之前数据结构里有个约瑟夫问题感觉就能用上✅️要求链表一趟遍历完成不能扫两遍4.虚拟头结点什么时候用什么时候不用题目行为是否推荐 dummyHead删除结点有可能删原头✅ 用新建链表尾插法拼接结点✅ 用查询、遍历、求长度、找中点、判环❌ 不用链表反转可选大部分写法不用
LeetCode19.删除链表的倒数第N个结点
题目代码class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); //因为删除的可能是头结点所以用虚拟头结点更方便避免分类讨论 dummyHead-next head; ListNode* slow dummyHead; ListNode* fast dummyHead; while(fast!NULLn--){//防止操作空指针 fastfast-next; } fastfast-next; while(fast!NULL){ fastfast-next; slowslow-next; } slow-nextslow-next-next;//删节点操作 return dummyHead-next; } };思路快慢指针结合虚拟头结点。利用快慢指针实现对链表的遍历解决链表无法定位“倒数第N个结点”的痛点因为当快指针到达链表末尾的时候慢指针正好位于要删除的结点的前一个~我们直接一个 slow-nextslow-next-next;就可以实现删除操作啦~至于虚拟头结点的存在是为了避免链表只有一个结点的情况这样的话就不需要特殊讨论了有个dummyhead比较方便统一写代码~小结1.为啥会出现多出来的一行fastfast-next?让fast实际比slow多走n1步因为最终我们的slow其实是在被删除结点前的位置哦~2. while(fast!NULLn--)指的是 fast 不为空且n03.快慢指针一般用于什么时候✅️链表不知道长度要找倒数 / 中间位置本题就是显而易见啊✅️判断链表有没有环这个有印象之前数据结构里有个约瑟夫问题感觉就能用上✅️要求链表一趟遍历完成不能扫两遍4.虚拟头结点什么时候用什么时候不用题目行为是否推荐 dummyHead删除结点有可能删原头✅ 用新建链表尾插法拼接结点✅ 用查询、遍历、求长度、找中点、判环❌ 不用链表反转可选大部分写法不用