1 #include<iostream>
 2 using namespace std;
 3 typedef struct Node
 4 { 
 5     int data;
 6     struct Node *next;
 7 }Node,*LinkList; 
 8 void creat(LinkList &p)
 9 {//后插法创建链表
10     Node *s,*r;
11     p = new Node;
12     p->next = NULL;
13     r = p;
14     while(1)
15     {
16         s = new Node;
17         cin >> s->data;
18         if(s->data == -1) break;
19         s->next = NULL;
20         r->next = s;
21         r = s;
22     }
23 }
24 Node *merge(LinkList La,LinkList Lb)
25 {
26     Node *Lc,*pa,*pb,*pc,*ptr;
27     pa = La->next;
28     pb = Lb->next; 
29     Lc = La;
30     pc = La;
31     while(pa && pb)
32     {
33         if(pa->data < pb->data)
34         {
35             pc->next = pa;
36             pc = pa;
37             pa = pa->next;
38         }
39         else if(pa->data > pb->data)
40         {
41             pc->next = pb;
42             pc = pb;
43             pb = pb->next;
44         }
45         else
46         {
47             pc->next = pa;
48             pc = pa;
49             pa = pa->next;
50             pc->next = pb;
51             pc = pb;
52             pb = pb->next;
53         }
54     }
55     pc->next = pa?pa:pb;
56     return Lc;
57 }
58 void output(LinkList Lc)
59 {
60     Node *m;
61     m = Lc->next;
62     int count = 0;
63     if(m)
64     {
65         while(m)
66         {
67             if(count == 0) cout << m->data;
68             else cout << " " << m->data;
69             m = m->next;
70             count++;
71         }
72     }
73     else cout << "NULL";
74 }
75 int main()
76 {
77     Node *La,*Lb,*Lc;
78     creat(La);
79     creat(Lb);
80     Lc = merge(La,Lb);
81     output(Lc);
82 }