如何将两个升序链表合并为一个降序链表?
算法的时间复杂度要求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"); }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 3无用