非递减单链表的合并仍为非递减的c语言代码

以下是一个利用归并排序实现非递减单链表合并的 C 代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node *merge(Node *list1, Node *list2) {
    Node *head = (Node *) malloc(sizeof(Node));
    Node *curr = head;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            curr->next = list1;
            list1 = list1->next;
        } else {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    if (list1) {
        curr->next = list1;
    } else if (list2) {
        curr->next = list2;
    }
    return head->next;
}

Node *merge_sort(Node *head) {
    if (!head || !head->next) {
        return head;
    }
    Node *slow = head, *fast = head, *prev = head;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    Node *left = head, *right = slow;
    prev->next = NULL;
    left = merge_sort(left);
    right = merge_sort(right);
    return merge(left, right);
}

void print_list(Node *head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    Node *list1 = (Node *) malloc(sizeof(Node));
    Node *list2 = (Node *) malloc(sizeof(Node));
    Node *node1 = (Node *) malloc(sizeof(Node));
    Node *node2 = (Node *) malloc(sizeof(Node));
    Node *node3 = (Node *) malloc(sizeof(Node));
    Node *node4 = (Node *) malloc(sizeof(Node));
    Node *node5 = (Node *) malloc(sizeof(Node));
    Node *node6 = (Node *) malloc(sizeof(Node));

    node1->val = 1;
    node2->val = 2;
    node3->val = 3;
    node4->val = 4;
    node5->val = 5;
    node6->val = 6;

    list1->next = node1;
    node1->next = node3;
    node3->next = node5;
    node5->next = NULL;

    list2->next = node2;
    node2->next = node4;
    node4->next = node6;
    node6->next = NULL;

    Node *head = merge_sort(merge(list1->next, list2->next));

    print_list(head);

    return 0;
}

输入：

1 3 5 2 4 6

输出：

1 2 3 4 5 6