写算法c语言 将两个非递减的有序链表合并为一个非递增的 有序链表。要求结果链表仍使用原来两个链表的存储空 间，不另外占用其它的存储空间。表中允许有重复的数 据。

在 C 语言中，我们可以使用迭代或递归的方式来解决这个问题。这里提供一个简单的迭代解决方案：

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

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

// 合并函数
Node* mergeTwoLists(Node* list1, Node* list2) {
    // 初始化结果头结点
    Node* result = (list1 > list2) ? list2 : list1;
    
    // 当两个列表都还有元素
    while (list1 && list2) {
        if (list1->data <= list2->data) {
            // 把较小的值添加到结果，并移动指针
            result->next = list1;
            list1 = list1->next;
        } else {
            result->next = list2;
            list2 = list2->next;
        }
        
        // 结果的下一个指针永远指向当前处理过的较小值节点
        result = result->next;
    }

    // 如果其中一个列表还有剩余元素，则直接添加到结果链表尾部
    if (list1) {
        result->next = list1;
    } else if (list2) {
        result->next = list2;
    }

    return result;
}

// 测试示例
void printList(Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建测试链表
    Node* list1 = (Node*)malloc(sizeof(Node));
    list1->data = 1;
    list1->next = (Node*)malloc(sizeof(Node));
    list1->next->data = 3;
    list1->next->next = (Node*)malloc(sizeof(Node));
    list1->next->next->data = 5;
    list1->next->next->next = NULL;

    Node* list2 = (Node*)malloc(sizeof(Node));
    list2->data = 2;
    list2->next = (Node*)malloc(sizeof(Node));
    list2->next->data = 4;
    list2->next->next = (Node*)malloc(sizeof(Node));
    list2->next->next->data = 6;
    list2->next->next->next = NULL;

    // 合并链表
    Node* mergedList = mergeTwoLists(list1, list2);

    // 打印合并后的链表
    printList(mergedList);

    // 清理内存
    free(mergedList);
    return 0;
}

这个程序首先创建了两个非递减有序链表，然后通过 `mergeTwoLists` 函数合并它们，最后打印出合并后的链表。注意，这个实现不会分配额外的空间，因为它只在原始链表的节点之间操作。