Question

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

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

Answer 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);
}