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

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

如何将两个升序链表合并为一个降序链表?
算法的时间复杂度要求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 有卷积神经网络识别害虫的项目吗
  • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号
  • ¥15 算法使用了tf-idf,用手肘图确定k值确定不了,第四轮廓系数又太小才有0.006088746097507285,如何解决?(相关搜索:数据处理)
  • ¥15 彩灯控制电路,会的加我QQ1482956179
  • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
  • ¥15 (关键词-电路设计)
  • ¥15 如何解决MIPS计算是否溢出
  • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
  • ¥15 操作系统相关算法中while();的含义
  • ¥15 CNVcaller安装后无法找到文件