Việc xóa nút trong danh sách liên kết thường yêu cầu xử lý trường hợp đặc biệt với nút đầu. Sử dụng nút giả (dummy node) giúp đơn giản hóa thao tác này.

1. Xóa phần tử trùng lặp trong danh sách có thứ tự

Bài toán: LeetCode 83

struct ListNode* removeDuplicates(struct ListNode* head) {
    struct ListNode* prev = head;
    if (!prev) return head;
    
    struct ListNode* current = prev->next;
    while (current) {
        if (prev->val == current->val) {
            current = current->next;
            prev->next = current;
        } else {
            prev = current;
            current = current->next;
        }
    }
    return head;
}

2. Xóa toàn bộ phần tử trùng lặp

Bài toán: LeetCode 82

Giải pháp 1: Sử dụng mảng đếm

struct ListNode* removeDuplicatesAll(struct ListNode* head) {
    int count[301] = {0};
    struct ListNode* current = head;
    
    while (current) {
        count[current->val]++;
        current = current->next;
    }
    
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;
    
    while (head) {
        if (count[head->val] > 1) {
            struct ListNode* temp = head;
            head = head->next;
            prev->next = head;
            free(temp);
        } else {
            prev = head;
            head = head->next;
        }
    }
    return dummy.next;
}

Giải pháp 2: Kỹ thuật con trỏ kép

struct ListNode* removeDuplicatesAll2(struct ListNode* head) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;
    struct ListNode* current = prev->next;
    
    if (!current) return head;
    
    while (current) {
        if (current->next && current->val == current->next->val) {
            int target = current->val;
            while (current && current->val == target) {
                struct ListNode* temp = current;
                current = current->next;
                free(temp);
            }
            prev->next = current;
        } else {
            prev = current;
            current = current->next;
        }
    }
    return dummy.next;
}

3. Xóa nút có giá trị cụ thể

Bài toán: LeetCode 136

struct ListNode* removeNode(struct ListNode* head, int value) {
    struct ListNode dummy;
    struct ListNode* prev = &dummy;
    struct ListNode* current = head;
    prev->next = current;
    
    while (current) {
        if (current->val == value) {
            struct ListNode* temp = current;
            current = current->next;
            prev->next = current;
            free(temp);
        } else {
            prev = current;
            current = current->next;
        }
    }
    return dummy.next;
}

4. Xóa nút thứ N tính từ cuối

Bài toán: LeetCode 21

Giải pháp 1: Tính độ dài

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int length = 0;
    struct ListNode* current = head;
    
    while (current) {
        length++;
        current = current->next;
    }
    
    int target = length - n + 1;
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;
    current = head;
    int counter = 1;
    
    while (counter < target) {
        prev = current;
        current = current->next;
        counter++;
    }
    prev->next = current->next;
    return dummy.next;
}

Giải pháp 2: Con trỏ nhanh-chậm

struct ListNode* removeNthFromEnd2(struct ListNode* head, int n) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* fast = &dummy;
    struct ListNode* slow = &dummy;
    
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    
    while (fast->next) {
        slow = slow->next;
        fast = fast->next;
    }
    struct ListNode* temp = slow->next;
    slow->next = temp->next;
    return dummy.next;
}

5. Xóa nút khi không có tham chiếu đầu

Bài toán: LeetCode 237

void deleteNode(struct ListNode* node) {
    struct ListNode* nextNode = node->next;
    *node = *nextNode;
    free(nextNode);
}

6. Xóa nút có giá trị tồn tại trong mảng

Bài toán: LeetCode 3217

struct ListNode* removeElements(struct ListNode* head, int* nums, int size) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;
    struct ListNode* current = head;
    int presence[100001] = {0};
    
    for (int i = 0; i < size; i++) {
        presence[nums[i]] = 1;
    }
    
    while (current) {
        if (presence[current->val]) {
            struct ListNode* temp = current;
            current = current->next;
            prev->next = current;
            free(temp);
        } else {
            prev = current;
            current = current->next;
        }
    }
    return dummy.next;
}

7. Xóa nút có giá trị nhỏ hơn nút kế tiếp

Bài toán: LeetCode 2487

struct ListNode* removeNodes(struct ListNode* head) {
    if (!head) return NULL;
    head->next = removeNodes(head->next);
    return head->next && head->val < head->next->val ? head->next : head;
}

8. Xóa nút giữa danh sách

Bài toán: LeetCode 2095

struct ListNode* deleteMiddle(struct ListNode* head) {
    if (!head || !head->next) return NULL;
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* prev = head;
    
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = slow->next;
    return head;
}