将元素添加到已排序的链表 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

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

#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);
    }
}

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

Issue when adding element into sorted linked list C++

c++

sorting

templates

pointers

linked-list