题解

头插法的核心：

node->next = head;
head = node;

每次把新结点放到最前面，因此最终链表顺序与输入顺序相反。

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

struct Node {
    long long data;
    Node* next;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    Node* head = nullptr;

    for (int i=0;i<n;++i) {
        long long x;
        cin >> x;
        Node* node = new Node{x, head};
        head = node;
    }

    bool first=true;
    Node* p=head;
    while (p) {
        if (!first) cout << ' ';
        first=false;
        cout << p->data;
        p=p->next;
    }
    cout << '\n';

    while (head) {
        Node* t=head;
        head=head->next;
        delete t;
    }
    return 0;
}

时间复杂度 $O(n)$，额外链表空间 $O(n)$。