线性表的基本应用(一)：线性表的合并

要求：

分别建立两个按值递增排列的无重值的线性表La和Lb，然后将Lb中的所有元素值合并到线性表La中，要求合并后的La中的元素仍然按照递增排列且无重复值。要求估算操作的时间复杂度。

思路：

首先取出La与Lb的第一个元素值，分别记为a与b，若a>b，则将b插入a之前，然后取Lb的下一个元素b；若a=b，则取La与Lb中的下一个元素值，仍记为a与b；若a<b，则取La中的下一个元素a。如此操作直到取出La中所有的元素，最后将Lb表中所有剩余元素插入La尾部。用链表实现，预估操作的时间复杂度为O(n)。

#include <bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node * pNext;
}NODE,*PNODE;

class LinkedList
{
public:
    void createList(int cnt); //cnt代表创建时链表的长度
    void combineList(const LinkedList & B);
    bool insert(int num,int pos); //在pos前插入
    void show();
private:
    PNODE pHead = NULL;
    PNODE pTail = NULL;
    int len; //链表长度
};

void LinkedList::createList(int cnt)
{
    PNODE p = NULL;
    this->pHead = new NODE();
    pHead->pNext = NULL;
    this->pTail = pHead;
    for (int i = 1; i <= cnt; i++)
    {
        p = new NODE();
        printf("请输入第%d个结点的值：",i);
        scanf("%d",&(p->data));
        pTail->pNext = p;
        pTail = p; //pTail始终要指向最后一个结点
        pTail->pNext = NULL;
    }
    this->len = cnt;
    return;
}

//在第pos位置前插入一个元素，虽然本例用不到，但就当复习插入元素了
bool LinkedList::insert(int num,int pos)
{
    if (pos > len+1 || pos <=0)
    {
        cout<<"非法输入，插入失败！"<<endl;
        return false;
    }
    PNODE p = pHead,q;
    for (int i = 1; i <= pos-1; i++)
    {
        p = p->pNext;
    }
    q = new NODE();
    q->data = num;
    q->pNext = p->pNext;
    p->pNext = q;
    this->len++;
    return true;
}

void LinkedList::show()
{
    PNODE p = pHead->pNext;
    while (p != NULL)
    {
        cout<<p->data<<" " ;
        p = p->pNext;
    }
    cout<<endl;
}

void LinkedList::combineList(const LinkedList & B)
{
    PNODE pA,pB,p;
    //为了便于操作，定义pA、pB两个指针，分别指向La与Lb待操作数的前一个结点，p为动态分配临时指针
    pA = this->pHead;
    pB = B.pHead;
    while (pA->pNext != NULL)
    {
        if (pB->pNext == NULL) //如果Lb表比La表短，终止循环
            break;
        if (pA->pNext->data > pB->pNext->data)
        {
            p = new NODE();
            p->data = pB->pNext->data;
            p->pNext = pA->pNext;
            pA->pNext = p;
            this->len++;
            pB = pB->pNext;
        }
        else if (pA->pNext->data < pB->pNext->data)
        {
            pA = pA->pNext;
        }
        else
        {
            pA = pA->pNext;
            pB = pB->pNext;
        }
    }
    //如果Lb表比La表长，则要把多余部分拼接在La后面
    pB = pB->pNext; //此时pB指向的是倒数第二个结点，所以要先将其移到最后一个结点
    while (pB != NULL)
    {
        p = new NODE();
        p->data = pB->data;
        pA->pNext = p;
        pA = p; //pA始终要指向最后一个结点
        pA->pNext = NULL;
        this->len++;
        pB = pB->pNext;
    }
}

int main()
{
    LinkedList La,Lb;
    La.createList(5);
    La.show();
    Lb.createList(3);
    Lb.show();
    La.combineList(Lb);
    La.show();
    return 0;
}

main函数中的测试代码运行结果如下所示：