首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

按升序对链表进行排序并打印排序的列表

链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。按升序对链表进行排序并打印排序的列表,可以通过以下步骤实现:

  1. 首先,需要定义链表节点的数据结构。一个链表节点通常包含一个数据元素和一个指向下一个节点的指针。例如,可以使用以下的C++代码定义链表节点:
代码语言:txt
复制
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
  1. 创建一个链表,并向其中插入节点。可以根据具体需求选择不同的插入方法,例如头插法或尾插法。这里以头插法为例,假设要排序的链表为head,可以使用以下代码向链表中插入节点:
代码语言:txt
复制
ListNode* head = nullptr;  // 创建一个空链表

// 向链表中插入节点
void insertNode(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}
  1. 使用合适的排序算法对链表进行排序。常见的排序算法有冒泡排序、插入排序、选择排序、归并排序和快速排序等。这里以归并排序为例,可以使用以下代码对链表进行排序:
代码语言:txt
复制
// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 归并排序链表
ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;
    
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    
    return merge(left, right);
}

// 对链表进行排序并返回排序后的头节点
ListNode* sortList(ListNode* head) {
    return mergeSort(head);
}
  1. 打印排序后的链表。可以使用以下代码遍历链表并打印节点的值:
代码语言:txt
复制
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}

综上所述,按升序对链表进行排序并打印排序的列表的完整代码如下:

代码语言:txt
复制
#include <iostream>
using namespace std;

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

// 向链表中插入节点
void insertNode(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

// 归并排序链表
ListNode* mergeSort(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;
    
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    
    return merge(left, right);
}

// 对链表进行排序并返回排序后的头节点
ListNode* sortList(ListNode* head) {
    return mergeSort(head);
}

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

int main() {
    ListNode* head = nullptr;  // 创建一个空链表
    
    // 向链表中插入节点
    insertNode(head, 3);
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 5);
    insertNode(head, 4);
    
    cout << "原始链表:";
    printList(head);
    
    head = sortList(head);
    
    cout << "排序后的链表:";
    printList(head);
    
    return 0;
}

以上代码使用归并排序对链表进行排序,并打印排序后的链表。该算法的时间复杂度为O(nlogn),其中n是链表的长度。在实际应用中,可以根据具体需求选择不同的排序算法和链表操作方法。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的沙龙

领券