删除链表的中间节点

删除链表的中间节点

你需要从单链表中删除中间节点。使用从 0 开始的索引，中间节点是第 ⌊n / 2⌋ 个节点。

以下是高效的解决方法。

策略

使用两个指针通过一次遍历找到中间节点。

• 使用一个每次移动一步的慢指针。
• 使用一个每次移动两步的快指针。
• 当快指针到达末尾时，慢指针正好位于中间。
• 使用第三个指针来追踪慢指针的前一个节点。

逻辑

1. 处理边界情况。如果链表只有一个节点，返回 null。
2. 在头节点初始化慢指针和快指针。
3. 快指针移动两步，慢指针移动一步。
4. 更新 prev 指针，使其始终保持在慢指针的前一步。
5. 循环结束后，将 prev 节点连接到 slow 的下一个节点。这样就跳过了中间节点。

复杂度

• 时间复杂度：O(n)。你只需遍历一次链表。
• 空间复杂度：O(1)。你只使用了三个指针。

PHP 实现

function deleteMiddle(ListNode $head): ?ListNode
{
    if ($head->next == null) {
        return null;
    }

    $slow = $head;
    $fast = $head;
    $prev = null;

    while ($fast !== null && $fast->next !== null) {
        $prev = $slow;
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    $prev->next = $slow->next;

    return $head;
}

来源: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1