面试题：C++ 链表节点删除的实现

Question

请使用C++ 实现一个单链表，并编写一个函数用于删除链表中指定值的节点。假设链表节点结构如下： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 请在函数`void deleteNode(ListNode*& head, int val)`中实现删除操作，保证链表结构的正确性。

Answer 1

#include <iostream>

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

void deleteNode(ListNode*& head, int val) {
    if (head == nullptr) {
        return;
    }
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* current = head;
    while (current->next != nullptr && current->next->val != val) {
        current = current->next;
    }
    if (current->next != nullptr) {
        ListNode* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 辅助函数：释放链表内存
void freeList(ListNode* head) {
    ListNode* current = head;
    ListNode* nextNode;
    while (current != nullptr) {
        nextNode = current->next;
        delete current;
        current = nextNode;
    }
}

你可以使用以下方式测试该函数：

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    std::cout << "Original list: ";
    printList(head);

    deleteNode(head, 3);

    std::cout << "List after deletion: ";
    printList(head);

    freeList(head);
    return 0;
}