如何将两个升序链表合并为一个降序链表？

Question

如何将两个升序链表合并为一个降序链表？
算法的时间复杂度要求Ｏ(n)，空间复杂度要求Ｏ(1).
C语言实现。

Answer 1

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int value;
    struct Node*next;
}Node;
Node*function(Node*t1,Node*t2){
    Node*head=(Node*)malloc(sizeof(Node));
    head->next=NULL;
    Node*p,*q;
    p=t1,q=t2;
    while(p!=NULL&q!=NULL){
        Node*tmp=(Node*)malloc(sizeof(Node));
        if(p->value<q->value){
            tmp->value=p->value;
            p=p->next;
        }else{
            tmp->value=q->value;
            q=q->next;
        }
        tmp->next=head->next;
        head->next=tmp;
    }
    while(p!=NULL){
        Node*tmp=(Node*)malloc(sizeof(Node));
        tmp->value=p->value;
        tmp->next=head->next;
        head->next=tmp;
        p=p->next;
    }
    while(q!=NULL){
        Node*tmp=(Node*)malloc(sizeof(Node));
        tmp->value=q->value;
        tmp->next=head->next;
        head->next=tmp;
        q=q->next;
    }
    return head->next;
}
int main(){
    //1-3-5 
    Node*t=(Node*)malloc(sizeof(Node));t->value=1;
    t->next=(Node*)malloc(sizeof(Node));t->next->value=3;
    t->next->next=(Node*)malloc(sizeof(Node));t->next->next->value=5;
    t->next->next->next=NULL;
    //2-4-6
    Node*t1=(Node*)malloc(sizeof(Node));t1->value=2;
    t1->next=(Node*)malloc(sizeof(Node));t1->next->value=4;
    t1->next->next=(Node*)malloc(sizeof(Node));t1->next->next->value=6;
    t1->next->next->next=NULL;
    Node*result=function(t,t1);
    Node*p=result;
    while(p!=NULL){
        printf("%d\t",p->value);
        p=p->next;
    }
    system("pause");
}