Xóa nút ở giữa của danh sách liên kết

Xóa nút ở giữa của một danh sách liên kết

Bạn cần xóa nút ở giữa của một danh sách liên kết đơn. Nút ở giữa là nút thứ ⌊n / 2⌋ theo chỉ số bắt đầu từ 0.

Dưới đây là cách giải quyết bài toán này một cách hiệu quả.

Chiến lược

Sử dụng hai con trỏ để tìm nút ở giữa chỉ trong một lần duyệt.

• Sử dụng một con trỏ chậm (slow pointer) di chuyển từng bước một.
• Sử dụng một con trỏ nhanh (fast pointer) di chuyển hai bước mỗi lần.
• Khi con trỏ nhanh đi đến cuối danh sách, con trỏ chậm sẽ nằm ở vị trí giữa.
• Sử dụng thêm một con trỏ thứ ba để theo dõi nút đứng trước con trỏ chậm.

Logic thực hiện

1. Xử lý trường hợp biên. Nếu danh sách chỉ có một nút, hãy trả về null.
2. Khởi tạo con trỏ chậm và con trỏ nhanh tại nút đầu (head).
3. Di chuyển con trỏ nhanh hai bước và con trỏ chậm một bước.
4. Cập nhật con trỏ prev để luôn đứng sau con trỏ chậm một bước.
5. Khi vòng lặp kết thúc, hãy nối nút prev với nút đứng sau nút slow. Việc này sẽ bỏ qua nút ở giữa.

Độ phức tạp

• Độ phức tạp thời gian: O(n). Bạn chỉ duyệt qua danh sách một lần.
• Độ phức tạp không gian: O(1). Bạn chỉ sử dụng ba con trỏ.

Triển khai bằng 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;
}

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