C语言实现两个有序链表的递减合并算法

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建链表
Node* createLinkedList(int* arr, int length) {
    Node* head = NULL;
    Node* tail = NULL;
    
    for (int i = 0; i < length; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }    
    }
    
    return head;
}

// 合并两个有序链表为一个递减有序链表
Node* mergeLinkedList(Node* list1, Node* list2) {
    Node* head = NULL;
    
    // 判断空链表情况
    if (list1 == NULL) {
        return list2;
    } else if (list2 == NULL) {
        return list1;
    }
    
    // 选择头节点
    if (list1->data <= list2->data) {
        head = list1;
        list1 = list1->next;
    } else {
        head = list2;
        list2 = list2->next;
    }
    
    Node* tail = head;
    
    // 合并两个链表
    while (list1 != NULL && list2 != NULL) {
        if (list1->data <= list2->data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        
        tail = tail->next;
    }
    
    // 将剩余的节点连接到结果链表中
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }
    
    return head;
}

// 逆序链表
Node* reverseLinkedList(Node* head) {
    Node* prev = NULL;
    Node* curr = head;
    
    while (curr != NULL) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

// 打印链表
void printLinkedList(Node* head) {
    Node* curr = head;
    
    while (curr != NULL) {
        printf('%d ', curr->data);
        curr = curr->next;
    }
    
    printf("\n");
}

int main() {
    int arr1[] = {1, 3, 5, 7, 9};
    int arr2[] = {2, 4, 6, 8, 10};
    
    Node* list1 = createLinkedList(arr1, 5);
    Node* list2 = createLinkedList(arr2, 5);
    
    Node* mergedList = mergeLinkedList(list1, list2);
    Node* reversedList = reverseLinkedList(mergedList);
    
    printLinkedList(reversedList);
    
    return 0;
}

该算法中，首先定义了链表节点结构体Node，包含一个整型数据data和一个指向下一个节点的指针next。然后，通过createLinkedList函数创建两个有序链表A和B。接着，通过mergeLinkedList函数将链表A和链表B合并为一个有序链表C。最后，通过reverseLinkedList函数将有序链表C逆序得到递减有序链表，并通过printLinkedList函数打印结果链表C。