C语言实现链表的归并
时间: 2024-02-02 15:03:39 浏览: 29
以下是C语言实现链表归并的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 定义哨兵节点
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode *cur = dummy;
// 遍历两个链表,将较小的节点加入新链表中
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
// 将剩余的节点加入新链表中
if (l1) {
cur->next = l1;
} else {
cur->next = l2;
}
return dummy->next;
}
// 归并排序
struct ListNode* sortList(struct ListNode* head) {
if (!head || !head->next) {
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 mergeTwoLists(left, right);
}
// 创建链表
struct ListNode* createList(int arr[], int n) {
if (n == 0) {
return NULL;
}
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->val = arr[0];
head->next = NULL; struct ListNode *cur = head;
for (int i = 1; i < n; i++) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = arr[i];
node->next = NULL;
cur->next = node;
cur = cur->next;
}
return head;
}
// 打印链表
void printList(struct ListNode *head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
int arr[] = {4, 2, 1, 3};
int n = sizeof(arr) / sizeof(int);
struct ListNode *head = createList(arr, n);
printf("原链表:");
printList(head);
head = sortList(head);
printf("排序后的链表:");
printList(head);
return 0;
}
```