Delete The Middle Node of A Linked List

2095. 删除链表的中间节点

分析

特例处理：
- 如果链表为空，直接返回 nullptr
- 如果链表只有一个节点，删除后返回 nullptr
- 如果链表只有两个节点，删除第二个节点，直接将 head->next 设为 nullptr
计算链表长度：
- 遍历链表，计算其长度 n
定位中间节点的前一个节点：
- 根据 n / 2 ，找到中间节点的前一个节点
- 将该节点的 next 指针指向中间节点的下一个节点，从而跳过中间节点
返回结果：
- 返回删除中间节点后的链表头节点

时间复杂度

计算链表长度：需要遍历链表一次，时间复杂度为 O(n)
定位中间节点的前一个节点：需要遍历链表一次，时间复杂度为 O(n)

总时间复杂度：O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
public:
    ListNode* deleteMiddle(ListNode* head)
    {
        // 如果链表只有一个节点
        if (!head->next)
            return nullptr;

        // 如果链表只有两个节点
        if (!head->next->next)
        {
            head->next = nullptr;
            return head;
        }

        // 计算链表长度
        int len = 0;
        for (ListNode* p = head; p; p = p->next)
            ++len;

        // 找到中间节点的前一个节点
        ListNode* p = head;
        for (int i = 0; i < len / 2 - 1; ++i)
            p = p->next;

        // 删除中间节点
        p->next = p->next->next;

        return head;
    }
};