已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
输出样例:
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <malloc.h>
using namespace std;
typedef int Status;
typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
LNode *next;
}LNode,*LinkList;
LinkList endCreate()
{
LinkList L,p,s;
Elemtype e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
p=L;
cin>>e;
while (e!=-1)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
p->next=s;
p=s;
cin>>e;
}
p->next=NULL;
return L;
}
LinkList headCreate()
{
LinkList L,s;
Elemtype e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
cin>>e;
while (e!=-1)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=L->next;
L->next=s;
cin>>e;
}
return L;
}
void print(LinkList list)
{
LinkList e;
e=list->next;
if(!e)
{
cout<<"NULL";
} else {
while (e->next) {
cout << e->data << " ";
e = e->next;
}
cout << e->data;
}
}
void merge(LinkList L1,LinkList L2,LinkList &L3)
{
LinkList l1=L1->next,l2=L2->next,l3;
l3=L3=L1;
while (l1&&l2)
{
if (l1->data<=l2->data)
{
l3->next=l1;
l3=l1;
l1=l1->next;
} else
{
l3->next=l2;
l3=l2;
l2=l2->next;
}
}
l3->next=l1?l1:l2;
}
int main()
{
LinkList L1,L2,L3;
L1=endCreate();
L2=endCreate();
merge(L1,L2,L3);
print(L3);
}
|
这道题两点重点，第一是实现merge操作。传进去两个链表和第三个的引用，然后一直判断直到某一个结束，如果L3后边是L1说明L1还有剩下的，如果不是说明剩下的都是L2后边；
第二个是输出，需要注意如果是空就输出NULL，他是让打印出NULL而不是return。。。