用归并排序对链表进行排序
时间: 2023-07-08 21:52:21 浏览: 76
链表在归并排序中的实现和数组不同,我们需要使用快慢指针来找到链表的中间节点。下面是使用 C 语言实现链表归并排序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode* next;
};
// 分割链表
struct ListNode* splitList(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* temp = slow->next;
slow->next = NULL;
return temp;
}
// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
// 归并排序
struct ListNode* mergeSort(struct ListNode* head) {
if (!head || !head->next) {
return head;
}
struct ListNode* mid = splitList(head);
struct ListNode* left = mergeSort(head);
struct ListNode* right = mergeSort(mid);
return merge(left, right);
}
// 打印链表
void printList(struct ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
}
int main() {
// 创建链表
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 3;
head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->val = 2;
head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->next->val = 4;
head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->next->next->val = 1;
head->next->next->next->next = NULL;
// 排序链表
head = mergeSort(head);
// 打印链表
printList(head);
return 0;
}
```
在这个示例代码中,我们首先定义了一个链表节点结构体 `ListNode`,然后定义了 `splitList()` 函数用于分割链表,`merge()` 函数用于合并两个有序链表,`mergeSort()` 函数用于实现链表归并排序。最后,我们创建了一个链表,对其进行排序,并使用 `printList()` 函数打印排序后的链表元素。