题解 | 遍历链表

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {} // 构造函数初始化节点
};

int main() {
    int n;
    while (cin >> n) {
        Node* a = new Node(0); // 创建哑节点
        Node* r = a;           // 尾指针指向哑节点

        while (n--) {
            int x;
            cin >> x;
            Node* p = new Node(x); // 为新节点分配内存并初始化

            if (a->next == nullptr) { // 链表为空时直接插入
                a->next = p;
                r = p;
            } else {
                if (p->data >= r->data) { // 插入到链表末尾
                    r->next = p;
                    r = p;
                } else { // 插入到合适的位置
                    Node* k = a;
                    while (k->next != nullptr) {
                        if (k->next->data >= p->data) {
                            p->next = k->next;
                            k->next = p;
                            break;
                        }
                        k = k->next;
                    }
                }
            }
        }

        Node* k = a->next;
        while (k != nullptr) { // 输出链表内容
            cout << k->data << " ";
            k = k->next;
        }
        cout << endl;

        // 释放链表内存
        Node* temp;
        while (a != nullptr) {
            temp = a;
            a = a->next;
            delete temp;
        }
    }

    return 0;
}

一定要记得初始化和释放内存，否则是失败的