开发者社区> 问答> 正文

已知两个排序相同的单链表A.B,合并成一个新链表C并且不改变它的排序性的算法.

这个用C++怎么编啊??

展开
收起
知与谁同 2018-07-16 20:09:27 2657 0
1 条回答
写回答
取消 提交回答
  • 这是递增合并成递增,如果是递减,略加修改就可以了

    需要按数据类型定义自行修改其中的内容
    思路:
    设待合并有头结点单链表为a 和b,合并到c
    设置三个指针pa, pb 和pc 分别指向a, b 和c 的当前结点
    开始时, pa, pb 和pc 分别指向a, b 和c 的头结点
    pa 和pb 向后扫描,依次合并元素值小的结点到pc 的当前表尾,直到某个链表合并完毕
    某链表归并完成后,需要处理另一个链表剩余的元素

    void Merge(LinkList a, LinkList b, LinkList c)
    { // 单链表a 和b 元素不减,原地合并为递增有序链表c
    Node *pa, *pb, *pc;
    pa = a->next;
    pb = b->next;
    pc = c->next;
    while (pa && pb)
    {
    if (pa->data <= pb->data)
    {
    pc->next = pa;
    pc = pa;
    pa = pa->next;
    }
    else
    {
    pc->next = pb;
    pc = pb;
    pb = pb->next;
    }
    }
    pc->next = pa ? pa : pb; // 追加剩余结点
    free(a);
    free(b);
    }
    2019-07-17 22:49:52
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载