c++ - 向单链表添加值

Question

我在上 C++ 数据结构课，最近的家庭作业一直困扰着我好几天。它必须处理单链表的工作，而我们必须编写的方法之一与向列表中添加值有关。

首先，我们创建虚拟节点head:

template<typename T>
SLList<T>::SLList()
{
  head = new Node; // Node() is ok too
}

如果我是对的，这应该没有值(value)，不是吗？所以 head 应该是 NULL。到目前为止，这是我(在我教授的帮助下)设法创造的。

template<typename T>
void SLList<T>::add(const T& val) {
    bool duplicate = false;
    //Node *ptr = head->next;
    //cout << head->data;

    for (Node *ptr = head->next; ptr != NULL; ptr = ptr->next) {
    //while (ptr == NULL) {
        //ptr = ptr->next;
        // if ptr is initialized as head, the first node, then ptr != NULL
        // if ptr is initialized as head->next, which it should in order to
        // traverse from the node AFTER the head, then ptr == NULL
        // not exactly sure why.
        if (ptr->data == val) {
            duplicate = true;
            break;
        }
    }
    //Node *temp = new Node(val); // create new node with new element.
    //temp->next = ptr->next;
    //ptr->next = temp;

    if (duplicate) {
        cout << "Duplicate entry found: " << val << endl;
    }
}

我试过使用 for 和 while 循环，因为很多谷歌搜索结果在他们的答案中使用了 while 循环。我想做的是尝试向列表中添加一个值。如果该值已在该列表中，则不会添加。我正在尝试这样做:

SLList<int> iList;
iList.add(5);
iList.add(6);
iList.add(6);

当我寻求帮助时，有人告诉我应该将 *ptr 初始化为 head->next 以开始遍历虚拟节点之后的节点列表。我使用了 Visual Studio 的调试器，发现在将它初始化为 head->next 之后，程序从未进入 for 循环，我假设这是因为虚拟节点之后的节点失败了 if 语句 ptr != NULL。我不确定为什么会这样，因为当我有 Node *ptr = head 时，它会很好地遍历列表(尽管下面的行 if (ptr->data == val) 会将每个条目视为重复条目)。

我可能理解错了，但是 head 节点的值不应该是 NULL 吗？所以它不应该在 for 循环中传递 if 语句。

for 循环之后的三行似乎也有问题，因为当程序到达那里时，它只是崩溃并且无法向列表添加任何值，但我想我只会一步一个脚印。

这里可能有很多我误解的地方，所以任何帮助都将不胜感激。

Answer 1

尝试这样的事情:

template<typename T>
void SLList<T>::add(const T& val) {
    Node<T>* prev = head;
    for (Node<T>* ptr = head->next; ptr; ptr = ptr->next) {
        if (ptr->data == val) {
            std::cout << "Duplicate: " << val << '\n';
            return;
        }
        prev = ptr;
    }
    prev->next = new Node<T>(val);
}