实习目的：熟练掌握链表的建立及基本操作

问题描述：

1）实现链表的排序(升序)

提交前请将所有的提示信息去掉，只保留最后的输出结果。例如运行时：从键盘直接输入：

2 1 2
3 1 2 3 

输出结果为：

1
2
3

分别表示第一个链表元素个数为2，元素分别为 1,2 ；第二个链表元素个数为3，元素分别为1,2,3。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>

using namespace std;
class List;
class LinkNode
{
    friend class List;

protected:
    LinkNode *link;
    int data;

public:
    LinkNode(LinkNode *p = NULL) { link = p; }
    LinkNode(int num, LinkNode *p = NULL)
    {
        data = num;
        link = p;
    }
    ~LinkNode(){};
};
class List
{
protected:
    int all;
    LinkNode *first;

public:
    List();

    void input();
    void output();
    int remove(int &a);
    void merge(List *l2);
    int find(int a);
    void sort();
};
List::List()
{
    first = new LinkNode();
    all = 0;
}
void List::input()
{
    int num, val;
    cin >> num;
    while (num)
    {
        cin >> val;
        LinkNode *newnode = new LinkNode(val);
        newnode->link = first->link;
        first->link = newnode;
        num--;
    }
}
void List::output()
{
    LinkNode *node = first->link;
    while (node != NULL)
    {
        cout << node->data << endl;
        node = node->link;
    }
}
int List::remove(int &a)
{
    LinkNode *node = first;
    LinkNode *p;
    while (node->link != NULL)
    {
        if (node->link->data == a)
        {
            p = node->link;
            node->link = p->link;
            delete p;
            return 1;
        }
        node = node->link;
        return 0;
    }
}
int List::find(int a)
{
    LinkNode *node = first->link;
    while (node != NULL)
    {
        if (node->data == a)
        {
            return 1;
        }
        node = node->link;
    }
    return 0;
}
void List::merge(List *l2)
{
    for (LinkNode *node = l2->first->link; node != NULL; node = node->link)
    {
        if (!find(node->data))
        {
            LinkNode *newnode = new LinkNode(node->data);
            newnode->link = first->link;
            first->link = newnode;
        }
    }
}
void List::sort()
{
    for (LinkNode *node1 = first->link; node1 != NULL; node1 = node1->link)
    {
        for (LinkNode *node2 = node1->link; node2 != NULL; node2 = node2->link)
        {
            int j;
            if (node1->data > node2->data)
            {
                j = node2->data;
                node2->data = node1->data;
                node1->data = j;
            }
        }
    }
}
int main()
{
    int k = 2;
    List l1, l2, l3;
    l1.input();
    // l1.output();
    l2.input();
    // l2.output();
    l1.merge(&l2);
    l1.sort();
    l1.output();
    return 0;
}