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

我就是我 2022-07-10 14:28 178阅读 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 ####

不得使用数组！

#### Author ####

####  提示：会使用归并函数 ####

\#include <stdio.h>

\#include <stdlib.h>  
struct node  
\{  
    int date;  
    struct node \*next;  
\};  
struct node \*creat(int n)  
\{  
    struct node \*head, \*p, \*tail;  
    int i;  
    head = (struct node \*)malloc(sizeof(struct node));  
    head->next = NULL;  
    tail = head;  
    for(i = 0; i < n; i++)  
    \{  
        p = (struct node \*)malloc(sizeof(struct node));  
        scanf("%d", &p->date);  
        p->next = NULL;  
        tail->next = p;  
        tail = p;  
    \}  
    return (head);  
\};  
struct node \*merge(struct node \*head1, struct node \*head2)  
\{  
    struct node \*p1, \*p2, \*tail;  
    p1 = head1->next;  
    p2 = head2->next;  
    tail = head1;  
    free(head2);  
    while(p1&&p2)  
    \{  
        if(p1->date < p2->date)  
        \{  
            tail->next = p1;  
            tail = p1;  
            p1 = p1->next;  
        \}  
        else  
        \{  
            tail->next = p2;  
            tail = p2;  
            p2 = p2->next;  
        \}  
    \}  
    if(p1)  
    \{  
        tail->next = p1;  
    \}  
    else  
    \{  
        tail->next = p2;  
    \}  
    return (head1);  
\};  
void show(struct node \*head1)  
\{  
    struct node \*p;  
    p = head1->next;  
    while(p != NULL)  
    \{  
  
  
        if(p->next == NULL)  
            printf("%d\\n",p->date);  
        else  
            printf("%d ", p->date);  
        p = p->next;  
    \}  
\}  
int main()  
\{  
    int n, m;  
    struct node \*head1, \*head2;  
    scanf("%d%d", &n, &m);  
    head1 = creat(n);  
    head2 = creat(m);  
    head1 = merge(head1, head2);  
    show(head1);  
    return 0;  
\}

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1999/pid/2119.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1999/pid/2119.html