C++单链表插入排序：实现从大到小和从小到大排序

本文介绍如何使用 C++ 实现将无序整数插入到两个单链表中，并分别保证插入后一个单链表的数据从大到小排序，另一个单链表的数据从小到大排序。

代码实现

以下是完整的 C++ 代码：cpp#include using namespace std;

// 定义单链表节点struct ListNode { int val; ListNode* next;

ListNode(int value) : val(value), next(nullptr) {}};

// 插入节点到单链表 a，并保持从大到小排序ListNode* insertNodeA(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (head == nullptr || value >= head->val) { newNode->next = head; return newNode; }

ListNode* cur = head;    while (cur->next != nullptr && cur->next->val > value) {        cur = cur->next;    }

newNode->next = cur->next;    cur->next = newNode;    return head;}

// 插入节点到单链表 b，并保持从小到大排序ListNode* insertNodeB(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (head == nullptr || value < head->val) { newNode->next = head; return newNode; }

ListNode* cur = head;    while (cur->next != nullptr && cur->next->val < value) {        cur = cur->next;    }

newNode->next = cur->next;    cur->next = newNode;    return head;}

// 打印单链表void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << endl;}

int main() { ListNode* a = nullptr; ListNode* b = nullptr;

cout << '请输入 5 个无序整数，用空格分隔：' << endl;    for (int i = 0; i < 5; i++) {        int num;        cin >> num;        a = insertNodeA(a, num);        b = insertNodeB(b, num);    }

cout << '排序后的单链表 a 为：';    printList(a);

cout << '排序后的单链表 b 为：';    printList(b);

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

ListNode* curB = b;    while (curB != nullptr) {        ListNode* temp = curB;        curB = curB->next;        delete temp;    }

return 0;}

代码解释

定义单链表节点: ListNode 结构体表示单链表的节点，包含数据域 val 和指针域 next。2. 插入节点并排序: - insertNodeA 函数将节点插入到单链表 a 中，并保证插入后单链表 a 的数据从大到小排序。 - insertNodeB 函数将节点插入到单链表 b 中，并保证插入后单链表 b 的数据从小到大排序。3. 打印单链表: printList 函数遍历并打印单链表的每个节点的值。4. 主函数: - 创建两个空的单链表 a 和 b。 - 从键盘输入 5 个无序整数。 - 使用 insertNodeA 和 insertNodeB 函数将整数插入到对应的单链表中，并进行排序。 - 使用 printList 函数打印排序后的单链表。 - 最后，释放单链表的内存，避免内存泄漏。

总结

本文介绍了如何使用 C++ 实现单链表的插入排序，将无序整数序列分别构建为从大到小和从小到大排序的单链表。通过学习本例，你可以更好地理解单链表操作和排序算法。