C++获取单链表中匹配节点的前一个节点

Question

首先:这是作业问题的一部分，所以请随意提示答案或指出正确的方向，而不是直接回答。

我正在用 C++ 创建一个单链表，其中一个必需的函数是 void remove(const T& key) 如果值与传递给函数的键的值匹配，则删除给定节点.

我现在的想法是必须先找到要删除的节点，找到要删除的节点之前的节点，找到要删除的节点之后的节点。从那里我可以删除需要删除的节点，并将前一个节点设置为指向删除节点之后的节点。

相关函数如下:

链表.h

//Returns the node with passed in value key
ListNode<T>* find(const T& key) {
    ListNode<T>* currentNode = _head;
    while(currentNode != NULL && currentNode->data() != key){
        currentNode = currentNode->next();  
    }
    return currentNode; 
}

//Returns the node before the key
ListNode<T>* findPreviousNode(const T& key){
    ListNode<T>* previousNode;
    ListNode<T>* currentNode = _head;

    while(currentNode != NULL && currentNode->data() != key){
        previousNode = currentNode;
        currentNode = currentNode->next();  
    }
    return previousNode;
}

// Removes and deletes the first node in the linked list that has data
// equal to the  key
void remove(const T& key) {
    ListNode<T>* nodeToDelete = find(key);
    ListNode<T>* previousNode = findPreviousNode(key);
    ListNode<T>* nextNode = nodeToDelete->next();
    delete nodeToDelete;
    previousNode->setNext(nextNode);

}

我已经广泛测试了我的 find(const T& key) 函数并且它工作正常，所以我相信问题出在我的 findPreviousNode 函数中，但是当我遍历代码时它似乎工作正常。

在我看来，previousNode 将始终具有最后检查的元素，当找到匹配项时，它会返回尚未更新的 previousNode，因此它仍然包含紧接在匹配节点之前的节点，但这显然不是正确，我不确定为什么。当我运行代码时，我得到一个

segmentation fault (core dumped)

错误信息

这里有一些包含完整代码的 pastebin:

LinkedList.h http://pastebin.com/b4miZBzA

main.cpp(调用测试函数的方法)http://pastebin.com/0QGtUhjC

Answer 1

你显然遗漏了很多边缘案例。

您的 find() 函数没有处理找不到 key 的情况。在这种情况下，它返回 null，为此 findPreviousNode() 返回 previousNode 的垃圾值。

假设 find() 返回指向 head 的指针。然后您的 findPreviousNode() 再次返回未初始化的前一个节点指针。

尝试处理代码中的边缘情况。

假设这些都已处理，您的 remove() 函数应该可以正常工作。

此外，您实际上并不需要调用 find() 函数，然后您可以通过从 findPreviousNode() 返回适当的值来真正提高运行时间，因为您'正在运行两个不必要的循环，因此您可以节省运行时间。