删除链表指定节点.md

删除链表指定节点

问题描述

给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted

解决方案

**Tip:**对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可

算法代码如下：

Node* List_DeleteNode(Node *head, Node *toBeDeleted) {
    if (head == nullptr || toBeDeleted == nullptr) {
        return head;
    }

    Node *tmp = head;
    if (toBeDeleted->next == nullptr) {
        if (tmp == toBeDeleted) {
//            delete tmp;
            return nullptr;
        }
        while (tmp->next != toBeDeleted) {
            tmp = tmp->next;
        }
        if(tmp->next == toBeDeleted) {
//            delete tmp->next;
            tmp->next = nullptr;
        }
    } else {
        tmp = toBeDeleted->next;
        toBeDeleted->value = tmp->value;
        toBeDeleted->next = tmp->next;
//        delete tmp;
    }
    return head;
}

说明：如果使用new分配内存，在删除节点时需要通过delete释放内存，否则会造成内存泄露

测试用例如下：

TEST(LinkedList, List_DeleteNode) {
    Node nodeList[10];

    EXPECT_TRUE(nullptr == List_DeleteNode(nullptr, nullptr));
    EXPECT_TRUE(nullptr == List_DeleteNode(nullptr, nodeList));

    List_Init(nodeList, 10);
    EXPECT_TRUE("0 1 2 3 4 5 6 7 8 9 " == List_GetListString(List_DeleteNode(nodeList, nullptr)));
    List_Init(nodeList, 10);
    EXPECT_TRUE("1 2 3 4 5 6 7 8 9 " == List_GetListString(List_DeleteNode(nodeList, &nodeList[0])));
    List_Init(nodeList, 10);
    EXPECT_TRUE("0 1 2 3 4 6 7 8 9 " == List_GetListString(List_DeleteNode(nodeList, &nodeList[5])));
    List_Init(nodeList, 10);
    EXPECT_TRUE("0 1 2 3 4 5 6 7 8 " == List_GetListString(List_DeleteNode(nodeList, &nodeList[9])));

    List_Init(nodeList, 1);
    EXPECT_TRUE(nullptr == List_DeleteNode(nodeList, &nodeList[0]));
}