【C++】148 排序链表

2024-05-12 15:44

文章标签 c++ 链表排序 148

本文主要是介绍【C++】148 排序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

对链表进行升序排序，常见的做法是使用归并排序（Merge Sort）算法。这种算法适用于链表的排序，并且具有稳定性和时间复杂度为 O(n log n) 的优点。

以下是使用 C 语言实现的归并排序算法来对链表进行排序的示例代码：

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct ListNode {int val;struct ListNode *next;
};// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL) return l2;if (l2 == NULL) return l1;struct ListNode dummy;struct ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = (l1 != NULL) ? l1 : l2;return dummy.next;
}// 归并排序
struct ListNode* sortList(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head;}// 快慢指针找到中点struct ListNode *slow = head, *fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}struct ListNode* mid = slow->next;slow->next = NULL;// 递归排序左右两部分struct ListNode* left = sortList(head);struct ListNode* right = sortList(mid);// 合并排序后的左右两部分return merge(left, right);
}// 创建新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 打印链表
void printList(struct ListNode* head) {struct ListNode* curr = head;while (curr) {printf("%d -> ", curr->val);curr = curr->next;}printf("NULL\n");
}// 释放链表内存
void freeList(struct ListNode* head) {struct ListNode* curr = head;while (curr) {struct ListNode* temp = curr;curr = curr->next;free(temp);}
}int main() {// 创建示例链表：4 -> 2 -> 1 -> 3struct ListNode* head = createNode(4);head->next = createNode(2);head->next->next = createNode(1);head->next->next->next = createNode(3);printf("Original list: ");printList(head);// 对链表进行排序head = sortList(head);printf("Sorted list: ");printList(head);// 释放链表内存freeList(head);return 0;
}