LLLLLogic 2022-03-11 16:18 采纳率: 60%
浏览 355
已结题

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

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

  • 写回答

2条回答 默认 最新

  • 广大菜鸟 2022-03-11 17:09
    关注
    
    #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");
    }
    

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 3月19日
  • 已采纳回答 3月11日
  • 创建了问题 3月11日

悬赏问题

  • ¥15 ios 新安装app收不到fcm推送
  • ¥15 有没有实力的写手?有过成品的优先
  • ¥15 图像信息库的建立与识别
  • ¥15 韩国网站购物,KG支付的支付回调如何解决
  • ¥15 workstation导入ovf文件,报错,怎么解决呢?
  • ¥15 关于#c语言#的问题:构成555单稳态触发器,采用LED指示灯延时时间,对延时时间进行测量并显示(如楼道声控延时灯)需要Proteus仿真图和C语言代码
  • ¥15 workstation加载centos进入emergency模式,查看日志报警如图,怎样解决呢?
  • ¥50 如何用单纯形法寻优不能精准找不到给定的参数,并联机构误差识别,给定误差有7个?matlab
  • ¥15 workstation加载centos进入emergency模式,查看日志报警如图,没有XFS,怎样解决呢?
  • ¥15 应用商店如何检测在架应用内容是否违规?