面试题：C++ 链表与多线程安全

Question

假设你正在使用C++ 开发一个多线程环境下使用的链表数据结构。链表节点结构如下： ```cpp struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ``` 请设计并实现以下功能，同时保证多线程操作的安全性： 1. 一个函数`void safeInsert(ListNode*& head, int val)`，在链表头部安全插入新节点。 2. 一个函数`bool safeDelete(ListNode*& head, int val)`，安全删除链表中值为`val`的节点，并返回是否成功删除。 你可以使用C++ 标准库中的多线程相关工具（如`<mutex>`）来实现线程安全机制。

Answer 1

#include <mutex>
#include <iostream>

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

class ThreadSafeList {
private:
    std::mutex listMutex;
public:
    void safeInsert(ListNode*& head, int val) {
        std::lock_guard<std::mutex> lock(listMutex);
        ListNode* newNode = new ListNode(val);
        newNode->next = head;
        head = newNode;
    }

    bool safeDelete(ListNode*& head, int val) {
        std::lock_guard<std::mutex> lock(listMutex);
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr && curr->val != val) {
            prev = curr;
            curr = curr->next;
        }
        if (curr == nullptr) {
            return false;
        }
        if (prev == nullptr) {
            head = curr->next;
        } else {
            prev->next = curr->next;
        }
        delete curr;
        return true;
    }
};

你可以这样使用这个类：

int main() {
    ListNode* head = nullptr;
    ThreadSafeList list;
    list.safeInsert(head, 1);
    list.safeInsert(head, 2);
    std::cout << "Delete 2: " << (list.safeDelete(head, 2)? "Success" : "Failed") << std::endl;
    std::cout << "Delete 3: " << (list.safeDelete(head, 3)? "Success" : "Failed") << std::endl;
    return 0;
}