C++ 数组转换为排序链表

本文将介绍如何使用 C++ 将一个整型数组转换为一个排序链表。

思路

1. 排序数组: 首先，我们需要对整型数组进行排序，以确保链表中的节点值按从小到大的顺序排列。
2. 创建链表: 遍历排序后的数组，依次创建每个元素的节点，并将它们添加到链表中。

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createList(int* arr, int n) {
    sort(arr, arr + n); // 排序
    ListNode* head = new ListNode(0); // 创建头节点
    ListNode* cur = head;
    for (int i = 0; i < n; i++) {
        ListNode* node = new ListNode(arr[i]); // 创建新节点
        cur->next = node; // 将新节点添加到链表尾部
        cur = cur->next;
    }
    return head->next; // 返回链表的真正头节点
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val << ' '; // 使用单引号
        head = head->next;
    }
    cout << endl;
}

int main() {
    int arr[] = { 3, 1, 4, 2, 5 };
    int n = sizeof(arr) / sizeof(int);
    ListNode* head = createList(arr, n);
    printList(head);
    return 0;
}

代码解释

1. createList(int* arr, int n) 函数:

   • 使用 sort() 函数对数组进行排序。
   • 创建一个头节点 head，并初始化一个指针 cur 指向它。
   • 遍历排序后的数组，对于每个元素 arr[i]，创建新节点 node，并将其添加到链表尾部。
   • 最后返回链表的真正头节点 head->next。

2. printList(ListNode* head) 函数:

   • 使用 while 循环遍历链表，输出每个节点的值。

总结

本教程演示了如何使用 C++ 将一个整型数组转换为一个排序链表。该方法简单易懂，并提供了详细的代码解释。你可以根据自己的需要，修改代码以适应不同的场景。