Xóa node giữa danh sách liên kết trong C++

Giới thiệu

Xóa node giữa (middle node) của danh sách liên kết đơn. Sử dụng kỹ thuật slow-fast pointer (con trỏ chậm-nhanh).

Thuật toán Slow-Fast Pointer

• Slow pointer: Di chuyển 1 node/lượt
• Fast pointer: Di chuyển 2 node/lượt
• Khi fast đến cuối, slow sẽ ở giữa

Ví dụ

Danh sách: 1→2→3→4→5→6 (6 node)

Slow: 1→2→3 | Fast: 1→3→5→NULL

Node giữa = 3 (node thứ 3), xóa nó → 1→2→4→5→6

Lưu ý: Với số chẵn node, thường xóa node giữa bên trái (thứ n/2).

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

Node* deleteMiddleNode(Node* head) {
    if (!head) return NULL;
    if (!head->next) { // Chỉ 1 node
        delete head;
        return NULL;
    }
    
    Node* slow = head;
    Node* fast = head;
    Node* prev = NULL;
    
    while (fast && fast->next) {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }
    
    // slow là node giữa, prev là node trước nó
    prev->next = slow->next;
    delete slow;
    
    return head;
}

void printLinkedList(Node* node) {
    while (node) {
        cout << node->data << " -> ";
        node = node->next;
    }
    cout << "NULL" << endl;
}

int main() {
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    
    cout << "Truoc khi xoa: ";
    printLinkedList(head);
    
    head = deleteMiddleNode(head);
    
    cout << "Sau khi xoa: ";
    printLinkedList(head);
    
    return 0;
}

Kết quả chạy chương trình

Truoc khi xoa: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Sau khi xoa: 1 -> 2 -> 3 -> 5 -> 6 -> NULL

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt danh sách 1 lần
• Không gian: O(1) - chỉ dùng 3 con trỏ

So sánh: Tìm giữa bằng 2 pass vs 1 pass

Slow-fast nhanh hơn thực tế (ít duyệt bộ nhớ hơn) và thanh lịch hơn.

Ứng dụng của Slow-Fast Pointer

• Phát hiện chu trình (Cycle detection) - Floyd's algorithm
• Tìm node giữa
• Tìm node thứ k từ cuối
• Kiểm tra palindrome linked list

Kết luận

Slow-fast pointer là kỹ thuật kinh điển, hiệu quả cho nhiều bài toán danh sách liên kết. Xóa node giữa chỉ cần O(n) thời gian, O(1) không gian.