题解 | 遍历链表

建立大根堆并使用头插法建立升序链表

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iterator>
#include <queue>
using namespace std;

struct LinkNode {
    int data;
    LinkNode* next;
};

void printlist(LinkNode* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
}

int main() {
    int n, a[1001];
    priority_queue<int> pq; // 大根堆只存储数据
    // 建立头结点，头指针head始终指向头结点，无论链表是否为空
    LinkNode* head = new LinkNode;
    head->next = NULL;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            pq.push(a[i]);
        }
        // 建立大根堆并使用头插法建立升序链表
        while (!pq.empty()) {
            int out = pq.top();
            pq.pop();
            LinkNode* newnode = new LinkNode;
            newnode->data = out;
            newnode->next = NULL;
            if (head->next == NULL) { // 是第一个结点，直接插到头结点后面
                head->next = newnode;
            }
            else {
                newnode->next = head->next;
                head->next = newnode;
            }
        }
        printlist(head->next); // 传入第一个有效数据结点
        printf("\n");
    }
    return 0;
}