数据结构 删除链表的中间结点

思路与算法

由于链表不支持随机访问，因此常见的找出链表中间节点的方法是使用快慢指针：即我们使用两个指针 textit{fast}fast 和 textit{slow}slow 对链表进行遍历，其中快指针 textit{fast}fast 每次遍历两个元素，慢指针 textit{slow}slow 每次遍历一个元素。这样在快指针遍历完链表时，慢指针就恰好在链表的中间位置。

在本题中，我们还需要删除链表的中间节点，因此除了慢指针 textit{slow}slow 外，我们再使用一个指针 textit{pre}pre 时刻指向 textit{slow}slow 的前一个节点。这样我们就可以在遍历结束后，通过 textit{pre}pre 将 textit{slow}slow 删除了。

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) 
    {
        if(head->next==nullptr)return nullptr;
        ListNode* slow=head,*fast=head,*prev=nullptr;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            prev=slow;
            slow=slow->next;
        }
        prev->next=prev->next->next;
        return head;
    }
};