删除链表的中间节点

删除链表的中间节点

一、题目

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

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

leetcode：https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/

二、思路

当长度为1 时，不删除；长度为 2 时，删除第1 个节点；长度为3时，删除第 1 个节点；长度为 4 时，删除第 2 个节点；长度为 5 时，删除第 2 个节点。(下标以 0 开始)

我们可以看到长度每增加 2，待删除节点增加 1。空链表和长度为 1 和 长度为 2 的链表我们应该特殊处理。

三、code

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* get_list(const std::vector<int>& vec) {
    ListNode* node = new ListNode(vec[0]);
    ListNode* tmp = node;
    for (size_t i = 1; i < vec.size(); ++i) {
        tmp->next = new ListNode(vec[i]);
        tmp = tmp->next;
    }
    return node;
}

void print_list(ListNode* node) {
    for (; node != nullptr;) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        // 空链表和长度为 1 的链表直接返回
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        // 长度为 2 的链表，要更新头节点
        if (head->next->next == nullptr) {
            head->next = nullptr;
            return head;
        }
        // 其余情况
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = slow;
        for (; fast != nullptr && fast->next != nullptr;) {
            fast = fast->next->next;
            // 在 slow 走之前先保存他的前一个节点
            prev = slow;
            slow = slow->next;
        }
        prev->next = prev->next->next;
        return head;
    }
};

int main() {
    Solution s;
    ListNode* head = get_list({1});
    print_list(head);
    ListNode* res = s.deleteMiddle(head);
    print_list(res);
    return 0;
}