实现对两个有序表（非递减有序）进行合并：

Question

有序表使用顺序存储结构，元素类型为int；

设两个有序顺序表分别为La和Lb，对La和Lb进行合并生成有序顺序表Lc，合并完成后，分别输出La、Lb和Lc。

【输入形式】通过键盘分别输入La表元素个数和La表所有元素，Lb表元素个数和Lb表所有元素，且保证所输入的元素是非递减的，若当前元素比前一元素小，则本元素输入无效，重新输入

【输出形式】分别输出La、Lb和合并后的Lc。
【样例输入】

5

1 3 4 3 6 8

6

2 4 5 7 9 12

【样例输出】

There are 5 elements in La,which are:1 3 4 6 8

There are 6 elements in Lb,which are:2 4 5 7 9 12

There are 11 elements in Lc,which are:1 2 3 4 4 5 6 7 8 9 12

【样例说明】

输入样例中，第1行数据表示La的元素个数；第2行数据为La的元素，其中，第4个元素输入无效，重新输入6；第3行数据表示Lb的元素个数，第4行数据为Lb的元素

输出样例中，每个数据元素占4列列宽，左对齐

Answer 1

运行结果如下：

代码：

#include <iostream>
using namespace std;

struct StNode 
{
    int data;
    struct StNode* next;
};

//创建节点
StNode* CreateNode(int d)
{
    StNode* node = new StNode;
    node->data = d;
    node->next = 0;
    return node;
}
//创建链表
StNode* CreateList()
{
    StNode* head,*p,*t;
    int nn,i=0;
    head = 0;
    p = head;
    t = head;
    int data,dt2;
    cin >> nn; //
    while(i<nn)
    {
        cin >> data;
        if(i>0 && data <dt2)
            continue;
        dt2 = data;
        i++;
        t = CreateNode(data);
        if(head ==0)
        {
            head = t;
            p = head;
        }
        else
        {
            p->next = t;
            p = t;
        }
    }
    return head;
}
//打印链表
void Display(StNode* head)
{
    while(head)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

//链表逆序
StNode* Reverse(StNode* head)
{
    StNode *next = NULL;
    StNode *prev = NULL;
    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

//计算表长
int Length(StNode* head)
{
    int len = 0;
    while(head)
    {
        len++;
        head = head->next;
    }
    return len;
}

//合并链表
StNode* Merge(StNode* h1,StNode* h2)
{
    //因为原来的链表是非递减次序，所以需要先逆序
    StNode* list1 = Reverse(h1);
    StNode* list2 = Reverse(h2);


    //合并为非递增序列（按递减序列处理）
    StNode* head = 0;
    StNode* tmp = 0;
    StNode* pps = 0;

    if(list1->data >= list2->data)
    {
        head = list1;
        list1 = list1->next;
    }else 
    {
        head = list2;
        list2 = list2->next;
    }
    pps = head;

    while(list1 && list2 )
    {
        if(list1->data >= list2->data)
        {
            pps->next = list1;
            pps = list1;
            list1 = list1->next;
        }else 
        {
            pps->next = list2;
            pps = list2;
            list2 = list2->next;
        }
    }
    while(list1)
    {
        pps->next = list1;
        pps = list1;
        list1 = list1->next;
    }

    while(list2)
    {
        pps->next = list2;
        pps = list2;
        list2 = list2->next;
    }
    pps->next = 0;


    return head;
}


int main()
{
    //创建两个链表：输入非递减数列（即递增序列，如1 2 3 4 5或者1 2 2 3 4 5，回车符结束）
    StNode* list1 = CreateList();
    StNode* list2 = CreateList();
    int l1,l2;
    l1 = Length(list1);
    l2 = Length(list2);
    cout << "There are "<<l1 <<" elements in La,which are:";
    Display(list1);
    cout << "There are "<<l2 <<" elements in Lb,which are:";
    Display(list2);
    //合并
    StNode* hh = Merge(list1,list2);
    //计算长度
    int len = Length(hh);
    cout << "There are "<<len <<" elements in Lc,which are:";
    //打印链表
    Display(hh);
    return 0;
}