假设有两个按元素值递增有序排列的 线性表A和B,均以单链表作存储结构,请编 写算法将表A和表B归并成一个按元素非递减 有序(允许值相同)排列的线性表C。

假设有两个按元素值递增有序排列的
线性表A和B,均以单链表作存储结构,请编
写算法将表A和表B归并成一个按元素非递减
有序(允许值相同)排列的线性表C。

修改如下，供参考：

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc)// 算法2.17
{ // 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
    LinkList pa = La->next, pb = Lb->next, pc;
    Lc = pc = La; // 用La的头结点作为Lc的头结点
    while (pa && pb)//循环条件
    {
        if (pa->data <= pb->data)//摘取pa所指结点
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else {  //摘取pb所取结点
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;// 将非空表的剩余段插入pc后
    free(Lb);//deletd Lb; 释放Lb的头结点
    Lb = NULL;
}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{
//合并链表La和Lb，合并后的新表使用头指针Lc指向
pa=La->next;
pb=Lb->next;
//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa && pb)
{
if(pa->datadata){
pc->next=pa;
pc=pa;
pa=pa->next;
}
//取较小者La中的元素，将pa链接在pc的后面，pa指针后移
else if(pa->data>pb->data) {
pc->next=pb;
pc=pb;
pb=pb->next;
}
//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
else //相等时取La中的元素，删除Lb中的元素
{
pc->next=pa;
pc=pa;
pa=pa->next;
q=pb->next;
delete pb ;
pb =q;
}
}
pc->next=pa?pa:pb; //插入剩余段
delete Lb; //释放Lb的头结点
}