本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你一个链表的头节点head。删除链表的中间节点并返回修改后的链表的头节点head。长度为n链表的中间节点是从头数起第⌊n / 2⌋个节点下标从0开始其中⌊x⌋表示小于或等于x的最大整数。对于n1、2、3、4和5的情况中间节点的下标分别是0、1、1、2和2。示例 1输入head[1,3,4,7,1,2,6]输出[1,3,4,1,2,6]解释 上图表示给出的链表。节点的下标分别标注在每个节点的下方。 由于 n7值为7的节点3是中间节点用红色标注。 返回结果为移除节点后的新链表。示例 2输入head[1,2,3,4]输出[1,2,4]解释 上图表示给出的链表。 对于 n4值为3的节点2是中间节点用红色标注。示例 3输入head[2,1]输出[2]解释 上图表示给出的链表。 对于 n2值为1的节点1是中间节点用红色标注。 值为2的节点0是移除节点1后剩下的唯一一个节点。提示链表中节点的数目在范围[1, 10^5]内1 Node.val 10^5方法 快慢指针前置题目[[LeetCode 876. 链表的中间结点【快慢指针】简单]]。为了删除链表的中间节点我们要让慢指针少走一步移动到中间节点的前一个节点。怎么让慢指针少走一步可以先让快指针走两步少循环一次这样慢指针就少走一步了。特判只有一个节点的情况快指针没法走两步返回空节点。/** * 使用假的头节点时 * 奇数长度快指针 第二步为空 表示 慢指针已经到了 中间节点前一个 * 偶数长度快指针 第一步为空 表示 慢指针已经到了 中间节点前一个 * * 不使用假的头节点为了让慢指针少走一步可以让快指针抢跑两步 * 只有一个节点返回空 */classSolution{publicListNodedeleteMiddle(ListNodehead){if(head.nextnull){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点ListNodeslowhead;ListNodefasthead.next.next;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}slow.nextslow.next.next;// 删除 slow 的下一个节点returnhead;}}classSolution{public:ListNode*deleteMiddle(ListNode*head){if(head-nextnullptr){// 只有一个节点returnnullptr;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点ListNode*slowhead;ListNode*fasthead-next-next;while(fastfast-next){slowslow-next;fastfast-next-next;}slow-nextslow-next-next;// 删除 slow 的下一个节点returnhead;}};classSolution:defdeleteMiddle(self,head:Optional[ListNode])-Optional[ListNode]:ifhead.nextisNone:# 只有一个节点returnNone# 876. 链表的中间结点# 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点slowhead fasthead.next.nextwhilefastandfast.next:slowslow.nextfastfast.next.nextslow.nextslow.next.next# 删除 slow 的下一个节点returnheadfuncdeleteMiddle(head*ListNode)*ListNode{ifhead.Nextnil{// 只有一个节点returnnil}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点slow:head fast:head.Next.Nextforfast!nilfast.Next!nil{slowslow.Next fastfast.Next.Next}slow.Nextslow.Next.Next// 删除 slow 的下一个节点returnhead}implSolution{pubfndelete_middle(head:OptionBoxListNode)-OptionBoxListNode{ifhead.as_ref()?.next.is_none(){// 只有一个节点returnNone;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点letmutslowhead;letmutfasthead.as_ref()?.next.as_ref()?.next;whilefast.is_some()fast.as_ref()?.next.is_some(){slowslow.as_ref()?.next;fastfast.as_ref()?.next.as_ref()?.next;}// 只读引用 - 只读裸指针 - 可变裸指针letmutslowslowas*constOptionBoxListNodeas*mutOptionBoxListNode;// 可变裸指针 - 可变引用letslowunsafe{mut*slow};slow.as_mut()?.nextslow.as_mut()?.next.take()?.next;// 删除 slow 的下一个节点head}}vardeleteMiddlefunction(head){if(head.nextnull){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点letslowhead;letfasthead.next.next;while(fastfast.next){slowslow.next;fastfast.next.next;}slow.nextslow.next.next;// 删除 slow 的下一个节点returnhead;};structListNode*deleteMiddle(structListNode*head){if(head-nextNULL){// 只有一个节点returnNULL;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点structListNode*slowhead;structListNode*fasthead-next-next;while(fastfast-next){slowslow-next;fastfast-next-next;}slow-nextslow-next-next;// 删除 slow 的下一个节点returnhead;}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是链表的长度。空间复杂度O ( 1 ) O(1)O(1)。专题训练链表题单的【1.6 快慢指针】。
LeetCode 2095. 删除链表的中间节点【链表,快慢指针】中等
本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你一个链表的头节点head。删除链表的中间节点并返回修改后的链表的头节点head。长度为n链表的中间节点是从头数起第⌊n / 2⌋个节点下标从0开始其中⌊x⌋表示小于或等于x的最大整数。对于n1、2、3、4和5的情况中间节点的下标分别是0、1、1、2和2。示例 1输入head[1,3,4,7,1,2,6]输出[1,3,4,1,2,6]解释 上图表示给出的链表。节点的下标分别标注在每个节点的下方。 由于 n7值为7的节点3是中间节点用红色标注。 返回结果为移除节点后的新链表。示例 2输入head[1,2,3,4]输出[1,2,4]解释 上图表示给出的链表。 对于 n4值为3的节点2是中间节点用红色标注。示例 3输入head[2,1]输出[2]解释 上图表示给出的链表。 对于 n2值为1的节点1是中间节点用红色标注。 值为2的节点0是移除节点1后剩下的唯一一个节点。提示链表中节点的数目在范围[1, 10^5]内1 Node.val 10^5方法 快慢指针前置题目[[LeetCode 876. 链表的中间结点【快慢指针】简单]]。为了删除链表的中间节点我们要让慢指针少走一步移动到中间节点的前一个节点。怎么让慢指针少走一步可以先让快指针走两步少循环一次这样慢指针就少走一步了。特判只有一个节点的情况快指针没法走两步返回空节点。/** * 使用假的头节点时 * 奇数长度快指针 第二步为空 表示 慢指针已经到了 中间节点前一个 * 偶数长度快指针 第一步为空 表示 慢指针已经到了 中间节点前一个 * * 不使用假的头节点为了让慢指针少走一步可以让快指针抢跑两步 * 只有一个节点返回空 */classSolution{publicListNodedeleteMiddle(ListNodehead){if(head.nextnull){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点ListNodeslowhead;ListNodefasthead.next.next;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}slow.nextslow.next.next;// 删除 slow 的下一个节点returnhead;}}classSolution{public:ListNode*deleteMiddle(ListNode*head){if(head-nextnullptr){// 只有一个节点returnnullptr;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点ListNode*slowhead;ListNode*fasthead-next-next;while(fastfast-next){slowslow-next;fastfast-next-next;}slow-nextslow-next-next;// 删除 slow 的下一个节点returnhead;}};classSolution:defdeleteMiddle(self,head:Optional[ListNode])-Optional[ListNode]:ifhead.nextisNone:# 只有一个节点returnNone# 876. 链表的中间结点# 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点slowhead fasthead.next.nextwhilefastandfast.next:slowslow.nextfastfast.next.nextslow.nextslow.next.next# 删除 slow 的下一个节点returnheadfuncdeleteMiddle(head*ListNode)*ListNode{ifhead.Nextnil{// 只有一个节点returnnil}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点slow:head fast:head.Next.Nextforfast!nilfast.Next!nil{slowslow.Next fastfast.Next.Next}slow.Nextslow.Next.Next// 删除 slow 的下一个节点returnhead}implSolution{pubfndelete_middle(head:OptionBoxListNode)-OptionBoxListNode{ifhead.as_ref()?.next.is_none(){// 只有一个节点returnNone;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点letmutslowhead;letmutfasthead.as_ref()?.next.as_ref()?.next;whilefast.is_some()fast.as_ref()?.next.is_some(){slowslow.as_ref()?.next;fastfast.as_ref()?.next.as_ref()?.next;}// 只读引用 - 只读裸指针 - 可变裸指针letmutslowslowas*constOptionBoxListNodeas*mutOptionBoxListNode;// 可变裸指针 - 可变引用letslowunsafe{mut*slow};slow.as_mut()?.nextslow.as_mut()?.next.take()?.next;// 删除 slow 的下一个节点head}}vardeleteMiddlefunction(head){if(head.nextnull){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点letslowhead;letfasthead.next.next;while(fastfast.next){slowslow.next;fastfast.next.next;}slow.nextslow.next.next;// 删除 slow 的下一个节点returnhead;};structListNode*deleteMiddle(structListNode*head){if(head-nextNULL){// 只有一个节点returnNULL;}// 876. 链表的中间结点// 本题先让快指针走两步这样慢指针少走一步刚好落在中间节点的前一个节点structListNode*slowhead;structListNode*fasthead-next-next;while(fastfast-next){slowslow-next;fastfast-next-next;}slow-nextslow-next-next;// 删除 slow 的下一个节点returnhead;}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是链表的长度。空间复杂度O ( 1 ) O(1)O(1)。专题训练链表题单的【1.6 快慢指针】。
