单个链表，节点插入最低到最高节点值的问题

Question

我正在尝试在学习C++语言的同时构建一个链表，并实现从低到高的节点插入函数。我关注了互联网和教科书上的一些教程。

我有一个链表节点设置的结构，如下所示：

struct Node {
 private:
  int _data;
  Node *_next = nullptr;
 public:
  Node () : _data ((int) (NULL)), _next (nullptr) { /* */ };
  explicit Node (int &value) : _data (*&value), _next (nullptr) { /* */ };
  friend class LL;
};

我的LL类：

class LL {
 private:
  Node *first;
 public:
  LL () : first (nullptr)
  { /* */ };
  void PrintList ();
  void Push_front (int x);
  void Push_back (int x);
  void Delete (int x);
  void Clear ();
  void Reverse ();
  void LTH(int x);
};

那么我从最低到最大的类函数是：

void LL::LTH(int x)
{
  Node *current = this->first;
  Node *newNode = new Node (x);
  if (this->first == NULL || (current->_data) >= newNode->_data)
    {
      newNode->_next = this->first;
      this->first  = new Node (x);
    }
  else
    {
      current = this->first;
      while (current->_next!=NULL &&
             current->_next->_data < newNode->_data)
        {
          current = current->_next;
        }
      newNode->_next = current->_next;
      current->_next = new Node (x);
    }
}

My LL：PrintList((

void LL::PrintList ()
{
  if (this->first == nullptr)
    {
      std::cout << "List is empty.n";
      return;
    }
  Node *current = this->first;
  while (current != nullptr)
    {
      std::cout << current->_data << " ";
      current = current->_next;
    }
  std::cout << std::endl;
}

我的主要

LL list;
// Changed to for-loop, original is reading binary data random integers
for (int i = 0; i < 20; i++)
  {
    list.LTH(i);
  }
list.PrintList ();

然后，它输出从低到高，但跳过一些节点：

// Linked-List Nodes
41, 34, 74, 87, 33, 25, 69, 75, 85, 30, 79, 61, 38, 49, 73, 64, 57, 95, 61, 86
// Output: LL:LTH() (Lowest -> Highest)
25, 30, 38, 49, 57, 61, 86
// It's Missing (XX)
XX, XX, XX, XX, XX, 25, XX, XX, XX, 30, XX, 61, 38, 49, XX, XX, 57, XX, XX, 86

Answer 1

我从您的问题中链接的教程中的代码开始，并进行了一些更改。请注意，这不是实现这一点的更"现代"的方式，但它可能是了解一些相关机制的起点。

#include <iostream>
#include <initializer_list>
class LinkedList;
class ListNode
{
    int data_ = 0;
    ListNode *next_ = nullptr;
public:
    ListNode() = default;
    ListNode(int a)
        : data_(a) {};
    // I added this constructor, it should ease the insertions
    ListNode(int a, ListNode *n)
        : data_(a), next_(n) {};
    friend class LinkedList;
};
class LinkedList{
private:
    ListNode *first_ = nullptr;
public:
    LinkedList() = default;
    // I didn't want to write down your example as a bunch of list.add(42)...
    LinkedList(std::initializer_list<int> lst)
    {
        for (auto i : lst)
            add(i);   
    }
    // Just to make the code more readable
    bool is_empty() const noexcept
    {
        return first_ == nullptr;
    }
    // Only a small set of function are implemented
    void add(int a);
    void print();
    void clear();
    // The tutorial didn't implement a destructor, but you should study about RAII
    ~LinkedList()
    {
        clear();
    }
};
int main()
{
    LinkedList a {
        41, 34, 74, 87, 33, 25, 69, 75, 85, 30, 79, 61, 38, 49, 73, 64, 57, 95, 61, 86
    };
    a.print();
}
void LinkedList::add(int a)
{
    if (is_empty())
    {
        first_ = new ListNode(a);
    }
    else if (first_->data_ >= a)
    {
        first_ = new ListNode(a, first_);   
    }
    else
    {
        ListNode *current = first_;
        while ( current->next_  &&  current->next_->data_ < a )
        {
            current = current->next_;
        }
        current->next_ = new ListNode(a, current->next_);
    }
}
void LinkedList::print()
{
    if (is_empty())
    {
        std::cout << "List is empty.n";
    }
    else
    {
        std::cout << first_->data_;
        for ( ListNode *current = first_->next_; current != nullptr; current = current->next_)
        {
            std::cout << ", " << current->data_;
        }
        std::cout << 'n';
    }
}
void LinkedList::clear()
{
    for (ListNode *current = first_, *next; current; current = next)
    {
        next = current->next_;
        delete current;
    }
    first_ = nullptr;
}

在这里可以测试，输出蜂鸣

25, 30, 33, 34, 38, 41, 49, 57, 61, 61, 64, 69, 73, 74, 75, 79, 85, 86, 87, 95

Answer 2

这没有经过测试，但 imo 它应该可以工作。

void LL::LTH(int x)
{
    Node* newNode = new Node (x);
    Node* lowest = this->first;
    // if smaller than the first one, add it to the beginning.
    if(lowest->_data > newNode->_data) {
        newNode->_next = lowest;
        this->first = newNode;        
    } else {  
        // Loop until at the right position.
        lowest = lowest->_next;
        while (lowest->_next!=NULL && lowest->_data < newNode->_data) {
            lowest = lowest->_next;
        }
        // If not on last, ensure to keep track of the next.
        if(lowest->_next != NULL) {
          newNode->_next = lowest->_next;                   
        }
        // insert at the current position.
        lowest->_next = newNode; 
    }
}