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

亦凉 2022-07-12 04:27 116阅读 0赞

数据结构实验之链表四：有序链表的归并  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic  
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

**之前做过一次，时间长了链表的知识都忘了，这提醒了我代码要带注释。。。**

#include<stdio.h>
    #include<stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    int main()
    {
        int i, n, m;
        struct node *p1, *head1, *tail1, *p2, *head2, *tail2;
        head1 = (struct node *) malloc (sizeof(struct node));
        head1 -> next = NULL;
        tail1 = head1;
        head2 = (struct node *) malloc (sizeof(struct node));
        head2 -> next = NULL;
        tail2 = head2;
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++)
        {
            p1 = (struct node *) malloc (sizeof(struct node));
            scanf("%d", &p1 -> data);
            p1 -> next = NULL;
            tail1 -> next = p1;
            tail1 = p1;
        }
        for(i = 0; i < m; i++)
        {
            p2 = (struct node *) malloc (sizeof(struct node));
            scanf("%d", &p2 -> data);
            p2 -> next = NULL;
            tail2 -> next = p2;
            tail2 = p2;
        }
        p1 = head1 -> next;
        p2 = head2 -> next;
        tail1 = head1;//tail1当做指针用
        free(head2);//去掉头结点
        while(p1 && p2)//控制循环到两个序列其中一个结束
        {
            if(p1 -> data  < p2 -> data)
            {
                tail1 -> next = p1;
                tail1 = p1;
                p1 = p1 -> next;
            }
            else
            {
                tail1 -> next = p2;
                tail1 = p2;
                p2 = p2 -> next;
            }
        }
        if(p1)
        {
            tail1 -> next = p1;//最后一个为p1
        }
        else
        {
            tail1 -> next = p2;//最后一个为p2
        }
        p1 = head1 -> next;
        while(p1 != NULL)
        {
            if(p1 -> next == NULL)
                printf("%d\n", p1 -> data);
            else
                printf("%d ", p1 -> data);
            p1 = p1 -> next;
        }
        return 0;
    }