数据结构实验之链表四：有序链表的归并

骑猪看日落 2022-07-15 10:12 115阅读 0赞

### 数据结构实验之链表四：有序链表的归并 ###

Time Limit: 1000MS  Memory Limit: 65536KB

#### Problem Description ####

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

#### Input ####

第一行输入M与N的值；  
第二行依次输入M个有序的整数；  
第三行依次输入N个有序的整数。

#### Output ####

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

#### Example Input ####

6 5
    1 23 26 45 66 99
    14 21 28 50 100

#### Example Output ####

1 14 21 23 26 28 45 50 66 99 100

#### Hint ####

不得使用数组！

#### Author ####

#include<stdio.h>
    #include<stdlib.h>
    struct node
    {
    int data;
    struct node *next;
    };
    struct node *creat(struct node *head,int n)
    {
    int i,m;
    struct node *p,*q,*tail;
    q=head;
    for(i=0;i<n;i++)
    {
    
    p=(struct node *)malloc(sizeof(struct node));
    scanf("%d",&p->data);
    p->next=q->next;
    q->next=p;
    q=p;
    }
    return head;
    }
    int main()
    {
    int i,j,n,m,k,t;
    struct node *head1,*head2,*p,*q,*tail,*v,*u;
    scanf("%d %d",&n,&m);
    head1=(struct node *)malloc(sizeof(struct node));
    head1->next=NULL;
    head1=creat(head1,n);
    head2=(struct node *)malloc(sizeof(struct node));
    head2->next=NULL;
    head2=creat(head2,m);
    p=head1->next;
    q=head2->next;
    free(head2);
    head1->next=NULL;
    tail=head1;
    while(p&&q)
    {
    if(p->data<q->data)
    {
    v=p->next;
    p->next=tail->next;
    tail->next=p;
    tail=p;
    p=v;
    }
    else
    {
    u=q->next;
    q->next=tail->next;
    tail->next=q;
    tail=q;
    q=u;
    }
    }
    if(p)
    tail->next=p;
    if(q)
    tail->next=q;
    p=head1;
    p=p->next;
    i=0;
    while(p!=NULL)
    {
    if(i==0)
    printf("%d",p->data);
    else
    printf(" %d",p->data);
    p=p->next;
    i++;
    }
    printf("\n");
    }