力扣(LeetCode)2095. 删除链表的中间节点(C++)

快慢指针

设置哑结点，便于删除头结点。找到链表的中间结点，可以用快慢指针从头结点出发，慢指针最后停在中间结点。删除中间结点，应当找中间结点的前一个结点。于是想到加入哑结点，这样初始快慢指针既可以往前一个位置，又便于删除头结点。

这个过程可以抽象成下图。

加入哑结点后，偶数长度的链表，找到如图第 $1$ 个链表的位置。奇数长度链的链表，找到如图第 $2$ 个链表的位置。

偶数链表找对了中间结点的前一个结点。奇数链表多走一步找错了，考虑找如图第 $3$ 个链表的位置 ，就行了。

由于哑结点的存在，我们看到的奇数链表，对于计算机其实是偶数链表。(非空)偶数链表的终止条件一定是快指针为空，那么我们在快指针为空之前拦截它的移动，并且少让慢指针移动一步，就可以实现第 $3$ 个链表的状态。

提示 : 我们看到的偶数链表，对于计算机是奇数链表。奇数链表的终止条件一定是快指针的后继为空，所以拦截快指针没有影响。奇偶链表实现归一化删除。

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        auto dummy = new ListNode (-1);
        dummy ->next = head;
        auto s = dummy,f = dummy;
        while(f&&f->next){
            f=f->next;
            if(f->next) s=s->next;
            f=f->next;
        }
        s->next = s->next->next;
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 时间复杂度 : $O(n)$ ， $n$ 是链表长度 ，遍历链表时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(1)$ ，只使用了常量级空间。

AC