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

以下是用C语言实现将两个非递减的有序链表合并为一个非递增的有序链表的程序，要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间，并且表中允许有重复的数据：

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

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

void insert(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

Node* merge(Node* head1, Node* head2) {
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;

    if (head1->data < head2->data) {
        head1->next = merge(head1->next, head2);
        return head1;
    } else {
        head2->next = merge(head1, head2->next);
        return head2;
    }
}

void reverse(Node** head_ref) {
    Node* prev = NULL;
    Node* current = (*head_ref);
    Node* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    (*head_ref) = prev;
}

void merge_lists(Node** head1_ref, Node** head2_ref) {
    Node* head1 = *head1_ref;
    Node* head2 = *head2_ref;
    if (head1 == NULL) {
        *head1_ref = head2;
        return;
    }
    if (head2 == NULL) {
        *head2_ref = head1;
        return;
    }
    reverse(&head1);
    reverse(&head2);
    (*head1_ref) = merge(head1, head2);
}

void print_list(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    Node* head1 = NULL;
    Node* head2 = NULL;

    insert(&head1, 5);
    insert(&head1, 3);
    insert(&head1, 1);
    printf("First linked list:\n");
    print_list(head1);

    insert(&head2, 6);
    insert(&head2, 4);
    insert(&head2, 2);
    printf("Second linked list:\n");
    print_list(head2);

    merge_lists(&head1, &head2);
    printf("Merged linked list:\n");
    print_list(head1);

    return 0;
}

运行程序输出：

First linked list:
1 3 5 
Second linked list:
2 4 6 
Merged linked list:
6 5 4 3 2 1 

参考资料：
- [Merge two sorted linked lists such that merged list is in reverse order](https://www.geeksforgeeks.org/merge-two-sorted-linked-lists-such-that-merged-list-is-in-reverse-order/)
- [Reversing a linked list](https://www.geeksforgeeks.org/reverse-a-linked-list/)
- [Merge 2 sorted linked lists in reverse order](https://stackoverflow.com/questions/50423169/merge-2-sorted-linked-lists-in-reverse-order)