7-51 两个有序链表序列的合并（数组合并，数组模拟的链表合并）

166 阅读 0 评论 110 点赞

我是靠谱客的博主光亮篮球，这篇文章主要介绍7-51 两个有序链表序列的合并（数组合并，数组模拟的链表合并），现在分享给大家，希望可以做个参考。

7-51 两个有序链表序列的合并

分数 20

作者 DS课程组

单位浙江大学

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

复制代码

1
2
3
1 3 5 -1
2 4 6 8 10 -1

输出样例:

复制代码

1
1 2 3 4 5 6 8 10

一、简单的数组合并：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e6+10;
int a[maxn],b[maxn];
int res[maxn];
int idx1,idx2,idx;

int main()
{
    int v;
    while(scanf("%d",&v) , v!=-1)
        a[idx1++] = v;
    while(scanf("%d",&v),v!=-1)
        b[idx2++] = v;
    
    if(!idx1 && !idx2)
        puts("NULL");
    else
    {
        int i=0,j=0;
        while(i<idx1 && j<idx2)
        {
            if(a[i] < b[j])
                res[idx++] = a[i++];
            else 
                res[idx++] = b[j++];
        }
        while(i<idx1)
            res[idx++] = a[i++];
        while(j<idx2)
            res[idx++] = b[j++];
            
        for(i=0;i<idx;++i)
        {
            if(i != 0)
                printf(" ");
            printf("%d",res[i]);
        }
    }
    
}

二、数组模拟的链表合并：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e7+10;
int e[maxn],ne[maxn],idx,head;


void init()
{
    ne[head] = -1;
    idx = 1;
}

void insert(int k,int v)
{
    e[idx] = v;
    ne[idx] = ne[k];
    ne[k] = idx;
    ++idx;
}

int main()
{
    init();  //别忘记初始化
    
    int v;
    while(scanf("%d",&v) , v!=-1)
        insert(idx-1,v);
            
    int index = ne[head];
    while(scanf("%d",&v),v!=-1)
    {
        while(index < idx && ne[index] != -1 && e[ne[index]] < v)
            index = ne[index];  //寻找最后一个小于v的下标
        insert(index,v);
    }

    if(idx == 1)
        puts("NULL");
    else
    {
        int flag=1;
        for(int i = ne[head];i!=-1;i=ne[i])
        {
            if(flag)
                flag = 0;
            else    
                cout << ' ';
            cout << e[i];
        }
    }

    return 0;
}