在插入过程中对链表进行排序

Question

所以我正在尝试按降序将节点插入链表中，但是当我得到重复的数字并且找不到解决问题的好解决方案时，我很难。我要么遇到丢失的数字/程序崩溃，要么程序只列出 1 个数字无限次。

这是我

的代码，我认为它适用于"else"语句，这是我无法弄清楚的部分，我只是留下我的最后一个版本，这显然不起作用

void Link::insert(int number) {
    Node *news = new Node;
    news->number = number;
    if(first == NULL) {
        first = news;
    }
    if(news->number > first->number) {
        Node *temp = first;
        first = news;
        news->next = temp;
    } else {
        Node *temp = first;
        while (temp->next || news->number < temp->number) {
            temp=temp->next;
        }
        temp->next = news;
        news->next = temp->next;
    }
}

如果需要其他功能或我的主要功能.cpp请告诉我。

Answer 1

也许

    void Link::insert(int number){
Node *news = new Node;
news->number = number;
if(first == NULL){
    first = news;
    return;
}
for(Node *i=first, *pred=NULL;!i;i=i->next){
 if(i->number<number){
  if(i==first) {
   news->next=first;
   first=news;
  } else {
   pred->next=news;
   news->next=i;
  }
  break;
 }
 pred=i;
}
}

Answer 2

当您第一次插入时，它会进入您的第一个if条件，然后设置 first=news ，但之后它会再次检查news->number > first->number哪些是假的，因此不必要地进入 else 条件。因此，要么在第一个if块中添加return;，要么将其他人放在else块中。跟踪上一个元素

else{
    Node *temp=first,*prev=null;
    while (temp && (temp->next || news->number < temp->number)){
        prev=temp;
        temp=temp->next;
    }
    if(prev==null){
       news->next=first;first=news;
     }
    else{
        prev->next=news;news->next=temp;
    }
}

Answer 3

你应该交换最后 2 行，否则你有news->next = news，创建一个循环。

无论如何，我建议将函数分为 2 个(私有(部分：一个部分找到在之后插入Node*(或nullptr用于第一个位置(，以及插入方法(而且调试起来更容易(。

Node* Link::upper_bound(int value) const
{
    if (first == nullptr || first->number <= value) {
        return nullptr;
    }
    Node* node = first;
    Node* next = first->next;
    while (next && value < next->number) {
        node = next;
        next = node->next;
    }
    return node; // we have: node->number < value && (next == nullptr || value <= next->number)
}
void Link::insert_after(Node* node, int value)
{
    Node* new_node = new Node(value);
    if (node == nullptr) {
        new_node->next = first;
        first = new_node;
    } else {
       new_node->next = node->next;
       node->next = new_node;
    }
}

最后：

void Link::insert(int number) {
    insert_after(upper_bound(number), number);
}