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

思路：定义两个指针指向两个链表的头节点，比较两个指针所指节点的值，将较小节点从原链表中取出并插入结果链表中。重复此过程直到两个链表中有一个为空，然后将另一个链表中剩余的节点接入结果链表中即可。

代码实现如下：

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

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

void merge(Node *list1, Node *list2) {   //合并函数
    Node *p1 = list1->next;      //p1指向list1的第一个元素
    Node *p2 = list2->next;      //p2指向list2的第一个元素
    Node *q = NULL;              //q用来记录结果链表的最后一个元素
    list1->next = NULL;          //初始化list1，使其成为新链表的头结点
    while (p1 != NULL && p2 != NULL) {  //只要两个链表都不为空
        if (p1->data <= p2->data) {     //如果list1当前节点的值小于等于list2当前节点的值
            Node *t = p1->next;         //将list1当前节点取出
            p1->next = q;               //将list1的第一个节点插入结果链表的最前面
            q = p1;                     //更新结果链表的尾节点为list1当前插入的元素
            p1 = t;                     //p1指向下一个待插入的节点
        } else {                        //如果list2当前节点的值小于list1当前节点的值
            Node *t = p2->next;         //将list2当前节点取出
            p2->next = q;               //将list2的第一个节点插入结果链表的最前面
            q = p2;                     //更新结果链表的尾节点为list2当前插入的元素
            p2 = t;                     //p2指向下一个待插入的节点
        }
    }
    if (p1 != NULL) {                   //如果list1还有剩余的节点
        Node *t = p1->next;             //将剩余节点全部插入结果链表的最前面
        p1->next = q;
        q = p1;
        p1 = t;
    }
    if (p2 != NULL) {                   //如果list2还有剩余节点
        Node *t = p2->next;             //将剩余节点全部插入结果链表的最前面
        p2->next = q;
        q = p2;
        p2 = t;
    }
    list1->next = q;                    //将结果链表的头节点重新接上
}

int main() {
    Node *list1, *list2;
    list1 = (Node*)malloc(sizeof(Node));   //定义链表1
    list2 = (Node*)malloc(sizeof(Node));   //定义链表2

    list1->next = (Node*)malloc(sizeof(Node));  //定义链表1的第一个元素
    list1->next->data = 1;              //赋值为1

    list2->next = (Node*)malloc(sizeof(Node));  //定义链表2的第一个元素
    list2->next->data = 2;              //赋值为2

    Node *p1 = list1->next;
    Node *p2 = list2->next;

    for (int i = 2; i <= 10; i += 2) {   //给链表1赋值2到10的偶数
        p1->next = (Node*)malloc(sizeof(Node));
        p1->next->data = i;
        p1 = p1->next;
    }
    p1->next = NULL;

    for (int i = 3; i <= 11; i += 2) {   //给链表2赋值3到11的奇数
        p2->next = (Node*)malloc(sizeof(Node));
        p2->next->data = i;
        p2 = p2->next;
    }
    p2->next = NULL;
    printf("List 1: ");                 //输出链表1
    p1 = list1->next;
    while (p1 != NULL) {
        printf("%d ", p1->data);
        p1 = p1->next;
    }
    printf("\nList 2: ");               //输出链表2
    p2 = list2->next;
    while (p2 != NULL) {
        printf("%d ", p2->data);
        p2 = p2->next;
    }
    printf("\nAfter merging: ");         //输出合并后的结果
    merge(list1,list2);
    p1 = list1->next;
    while (p1 != NULL) {
        printf("%d ", p1->data);
        p1 = p1->next;
    }
    printf("\n");
    return 0;
}

输出结果：

List 1: 1 2 4 6 8 10 
List 2: 2 3 5 7 9 11 
After merging: 11 10 9 8 7 6 5 4 3 2 2 1