将元素添加到排序链表C++时出现问题

Question

我在作业中遇到了一个奇怪的问题，我应该编写一个模板方法以插入到排序的链表中。

这是奇怪的事情。如果我有一个链表，并且我要添加的值位于链表的末尾，则当我添加值时，倒数第二个之前的所有其他值以及新插入的值都会被删除。这是所发生情况的说明：

1->3->5->nullptr // starting linked list
add_ordered_i(list, 8); // add 8 to the linked list
5->8->nullptr // what ends up being output

在我进入这个问题之前，这里是我得到的模板化链表类。

#include <string>
#include <iostream>
#include <fstream>
template<class T>
class LN {
  public:
    LN ()                        : next(nullptr){}
    LN (const LN<T>& ln)         : value(ln.value), next(ln.next){}
    LN (T v, LN<T>* n = nullptr) : value(v), next(n){}
    T      value;
    LN<T>* next;
};
template<class T>
std::ostream& operator << (std::ostream& outs, LN<T>* l) {
  for (LN<T>* p = l; p != nullptr; p = p->next)
    std::cout << p->value << "->";
  std::cout << "nullptr";
  return outs;
}
template<class T>
void add_ordered_i (LN<T>*& l, T value)
{
}

以下是我对函数add_ordered_i的尝试：

template<class T>
void add_ordered_i (LN<T>*& l, T value) {
    LN<T>*& cur = l;
    LN<T>* prev = new LN<T>();
    if(cur == nullptr)  {
        cur = new LN<T>(value);
        return;
    }
    while(cur->next != nullptr)
    {
        if(value < cur->next->value || cur->next == nullptr)
            break;
        cur = cur->next;
    }
    if(cur->next == nullptr) {
        if(value < cur->value) {
            cur = new LN<T>(value, cur);
            return;
        }
        cur->next = new LN<T>(value);
        return;
    } else {
        prev = cur->next;
        cur->next = new LN<T>(value,prev);
        return;
    }
}

我不确定为什么会发生这种情况。特别是因为在main（）中我可以做：

while(list->next != nullptr)
    p = p->next
p->next = new LN<int>(5);

它将在列表末尾插入数字 5，无论当前有多少元素。我在函数中引用列表时做错了什么吗？或者是什么导致它删除了除上一个和新添加的元素之外的几乎所有元素？

Answer 1

那是因为cur是add_ordered_i中的引用，并且您有cur = cur->next也会修改l。

我

做了一些更改，它对我有用。

template<class T>
void add_ordered_i (LN<T>*& l, T value) {
    LN<T>* cur = l;//just a normal pointer will be fine
    if(cur == nullptr)  {
        l = new LN<T>(value);//a empty list
        return;
    }
    while(cur->next != nullptr)
    {
        if(value < cur->next->value)
            break;
        cur = cur->next;
    }
    if(cur == l) {
        l = new LN<T>(value, cur);//add to head of list
    } else {
        cur->next = new LN<T>(value,cur->next);
    }
}