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的最大整数。

对于n=1、2、3、4和5的情况，中间节点的下标分别是0、1、1、2和2。

示例 1：

输入：head=[1,3,4,7,1,2,6]输出：[1,3,4,1,2,6]解释： 上图表示给出的链表。节点的下标分别标注在每个节点的下方。 由于 n=7，值为7的节点3是中间节点，用红色标注。 返回结果为移除节点后的新链表。

示例 2：

输入：head=[1,2,3,4]输出：[1,2,4]解释： 上图表示给出的链表。 对于 n=4，值为3的节点2是中间节点，用红色标注。

示例 3：

输入：head=[2,1]输出：[2]解释： 上图表示给出的链表。 对于 n=2，值为1的节点1是中间节点，用红色标注。 值为2的节点0是移除节点1后剩下的唯一一个节点。

提示：

链表中节点的数目在范围[1, 10^5]内
1 <= Node.val <= 10^5

方法快慢指针

前置题目：[[LeetCode 876. 链表的中间结点【快慢指针】简单]]。

为了删除链表的中间节点，我们要让慢指针少走一步，移动到中间节点的前一个节点。怎么让慢指针少走一步？

可以先让快指针走两步，少循环一次，这样慢指针就少走一步了。

特判只有一个节点的情况（快指针没法走两步），返回空节点。

/** * 使用假的头节点时 * 奇数长度，快指针 第二步为空 表示 慢指针已经到了 中间节点前一个 * 偶数长度，快指针 第一步为空 表示 慢指针已经到了 中间节点前一个 * * 不使用假的头节点，为了让慢指针少走一步，可以让快指针抢跑两步 * 只有一个节点返回空 */classSolution{publicListNodedeleteMiddle(ListNodehead){if(head.next==null){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点ListNodeslow=head;ListNodefast=head.next.next;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}slow.next=slow.next.next;// 删除 slow 的下一个节点returnhead;}}

classSolution{public:ListNode*deleteMiddle(ListNode*head){if(head->next==nullptr){// 只有一个节点returnnullptr;}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点ListNode*slow=head;ListNode*fast=head->next->next;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}slow->next=slow->next->next;// 删除 slow 的下一个节点returnhead;}};

classSolution:defdeleteMiddle(self,head:Optional[ListNode])->Optional[ListNode]:ifhead.nextisNone:# 只有一个节点returnNone# 876. 链表的中间结点# 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点slow=head fast=head.next.nextwhilefastandfast.next:slow=slow.nextfast=fast.next.nextslow.next=slow.next.next# 删除 slow 的下一个节点returnhead

funcdeleteMiddle(head*ListNode)*ListNode{ifhead.Next==nil{// 只有一个节点returnnil}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点slow:=head fast:=head.Next.Nextforfast!=nil&&fast.Next!=nil{slow=slow.Next fast=fast.Next.Next}slow.Next=slow.Next.Next// 删除 slow 的下一个节点returnhead}

implSolution{pubfndelete_middle(head:Option<Box<ListNode>>)->Option<Box<ListNode>>{ifhead.as_ref()?.next.is_none(){// 只有一个节点returnNone;}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点letmutslow=&head;letmutfast=&head.as_ref()?.next.as_ref()?.next;whilefast.is_some()&&fast.as_ref()?.next.is_some(){slow=&slow.as_ref()?.next;fast=&fast.as_ref()?.next.as_ref()?.next;}// 只读引用 -> 只读裸指针 -> 可变裸指针letmutslow=slowas*constOption<Box<ListNode>>as*mutOption<Box<ListNode>>;// 可变裸指针 -> 可变引用letslow=unsafe{&mut*slow};slow.as_mut()?.next=slow.as_mut()?.next.take()?.next;// 删除 slow 的下一个节点head}}

vardeleteMiddle=function(head){if(head.next===null){// 只有一个节点returnnull;}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点letslow=head;letfast=head.next.next;while(fast&&fast.next){slow=slow.next;fast=fast.next.next;}slow.next=slow.next.next;// 删除 slow 的下一个节点returnhead;};

structListNode*deleteMiddle(structListNode*head){if(head->next==NULL){// 只有一个节点returnNULL;}// 876. 链表的中间结点// 本题先让快指针走两步，这样慢指针少走一步，刚好落在中间节点的前一个节点structListNode*slow=head;structListNode*fast=head->next->next;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}slow->next=slow->next->next;// 删除 slow 的下一个节点returnhead;}