Question

设A和B是两个单链表其表中元素递增有序试写一算法将A和B归并成一个按元素值递减有序的单链表C并要求辅

助空间为O(1)

Answer 1

node *mergelink(node *p, node *q)
{
node *h, *r;
h = (node*) malloc (sizeof(node));
h->next = NULL;
r = h;
while (p != NULL && q != NULL)
{
if (p->data <= q->data)
{
r->next = p;
r = p;
p = p->next;
}
else
{
r->next = q;
r = q;
q = q->next;
}
}

if (p == NULL)
r->next = q;
if (q == NULL)
r->next = p;

p = h->next;
h = h->next;
free(p);
return h;
}