已知两个排序相同的单链表A.B,合并成一个新链表C并且不改变它的排序性的算法.
收起
知与谁同
2018-07-16 20:09:27
2665
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