题目描述

分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。

输入

第一行输入M与N的值；

第二行依次输入M个有序的整数；

第三行依次输入N个有序的整数。

输出

输出合并后的单链表所包含的M+N个有序的整数。

示例输入

6 51 23 26 45 66 9914 21 28 50 100

示例输出

1 14 21 23 26 28 45 50 66 99 100

提示

不得使用数组！

1 #include 
       
         2 #include 
        
          3 typedef struct node 4 { 5     int data; 6     struct node *next ; 7 }Node; 8 Node *Creatlist(int n) 9 {10     int i;11     Node * head, * p, * tail;12     head=(Node*)malloc(sizeof(Node));13     head->next =NULL;14     tail=head;15     for(i=1;i<=n;i++)16     {17         p=(Node *)malloc(sizeof(Node));18         scanf("%d",&p->data);19         p->next=NULL;20         tail->next=p;21         tail=p;22     }23     return head;24 }25 Node *Merger(Node * head1, Node * head2)26 {27     Node *p1,*p2,*tail ;28     p1=head1->next ;29     p2=head2->next ;30     tail=head1 ;31     free( head2 ) ;32     while(p1 && p2)33     {34         if(p1->data < p2->data)35         {36             tail->next=p1 ;37             tail=p1 ;38             p1 = p1->next ;39         }40         else41         {42             tail->next=p2 ;43             tail=p2 ;44             p2=p2->next ;45         }46     }47     if(p1)48         tail->next = p1 ;49     else50         tail->next = p2 ;51     return (head1) ;52 }53 void Dis_list(Node * l)54 {55     Node *r ;56     r=l ;57 58     while(r->next->next!=NULL)59     {60         printf("%d ",r->next->data) ;61         r=r->next ;62     }63     printf("%d\n", r->next->data) ;64 }65 int main()66 {67     Node *head1, *head2, *p ;68     int n, m ;69     scanf("%d %d",&n,&m) ;70     head1=Creatlist(n) ;71     head2=Creatlist(m) ;72     p=Merger(head1,head2) ;73     Dis_list(p) ;74     return 0 ;75 }