如何在C++单链表结构体中实现升序添加元素的push函数？

下面是完成后的代码，重点实现了list结构体中的push函数，确保新元素按升序插入链表：

#include <iostream>
using namespace std;

struct Node 
{
    int info;
    Node* next;
    Node(int value) 
    {
        info = value; 
        next = nullptr;
    }
    Node()
    {
        info = 0; // int类型用0代替NULL更合理
        next = nullptr;
    }
};

struct list 
{
    Node* first;
    Node* last;

    list() 
    {
        first = nullptr; 
        last = nullptr;
    }

    void push_back(int info) 
    {
        Node* lp = new Node(info);
        if (first == nullptr) 
        {
            first = lp;
            last = lp;
            return;
        }
        last->next = lp;
        last = lp;
    }
    
    void push(int info) 
    {
        Node* new_node = new Node(info);
        
        // 情况1：链表为空，直接作为首尾节点
        if (first == nullptr) {
            first = new_node;
            last = new_node;
            return;
        }
        
        // 情况2：插入到表头（新元素小于等于首元素）
        if (new_node->info <= first->info) {
            new_node->next = first;
            first = new_node;
            return;
        }
        
        // 情况3：找到中间或尾部的插入位置
        Node* current = first;
        while (current->next != nullptr && current->next->info < new_node->info) {
            current = current->next;
        }
        
        // 插入新节点
        new_node->next = current->next;
        current->next = new_node;
        
        // 如果插入到尾部，更新last指针
        if (new_node->next == nullptr) {
            last = new_node;
        }
    }

    void print() {
        if (first == nullptr) 
        {
            return;
        }
        Node* pl = first;
        while (pl) 
        { 
            cout << pl->info << " ";
            pl = pl->next;
        }
        cout << endl;
    }
};

struct Node* sortedMerge(struct Node* a, struct Node* b)
{
    if (a == NULL) {
        return b;
    }

    else if (b == NULL) {
        return a;
    }

    struct Node* result = NULL;

    if (a->info <= b->info)
    {
        result = a;
        result->next = sortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = sortedMerge(a, b->next);
    }

    return result;
}


int main() 
{
    list my_list;
    my_list.push(27);
    my_list.push(4);
    my_list.push(11);
    my_list.print(); // 输出：4 11 27
}

实现说明 #

• 空链表处理：直接将新节点设为链表的首节点和尾节点。
• 表头插入：当新元素小于等于首节点值时，将新节点链接到原首节点前，更新首节点指针。
• 中间/尾部插入：遍历链表找到第一个后续节点值大于新元素的位置，插入新节点；若插入到尾部，同步更新尾节点指针，保证后续push_back操作正常。
• 修正了Node默认构造函数中info = NULL的问题，NULL是指针类型，给int类型赋值用0更恰当。

内容的提问来源于stack exchange，提问作者Бублик Суслик