将两个递增的有序链表La和Lb合并为一个递增的有序链表Lc-创新互联

题目：将两个递增的有序链表La和Lb合并为一个递增的有序链表Lc。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间，表中不允许有重复的数据
算法思想：假设待合并的链表为La和Lb，合井后的新表使用头指针 Lc (Lc的表头结点设为La的表头结点)指向。pa和pb分别是链表La和Lb的工作指计，初始化为相应链表的首元结点。从首元结点开始进行比较，当两个链表La和Lb均未到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后的表中无重复的元素。当一个表到达表尾结点为空时，将非空表的剩余元素直接链接在Lc表的最后，最后释放链表Lb的头结点。

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc)
{//将两个递增的有序链表La和Lb合并为一个递增的有序链表Lc
    LinkList pa, pb, pc, Lc,p;
    pa = La->next;//pa是链表La的工作指针，初始化为首元结点
    pb = Lb->next;//pb是链表Lb的工作指针，初始化为首元结点
    Lc = La = pc;//用La的头结点作为Lc的头结点
    while (pa && pb)
    {if (pa->data< pb->data)
        {//取较小者La中的元素，将pa链接在pc的后面，pa指针后移
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else if (pa->data >pb->data)
        {/取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else
        {//相等时取La中的元素，删除Lb中的元素
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            p = pb->next;
            delete pb;
            pb = p;
        }
    }
    pc->next = pa ? pa : pb;//将非空表的剩余元素直接链接在Lc表的最后
    delete Lb;//释放Lb的头结点
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧