数据结构有序链表问题。Writeafunctiontomergetwosortedlinkedlists.Theinputlistshavetheirelementsinsortedorder,fromlowesttohighest.Theoutputlistshouldalsobesortedfromlowesttohighest.Youralgorithmshouldruni

Question

数据结构有序链表问题。
Write a function to merge two sorted linked lists. The input lists have their elements in sorted order, from lowest to highest. The output list should also be sorted from lowest to highest. Your algorithm should run in linear time on the length of the output list.

Answer 1

typedef struct node
{
datatype data;
struct node *next;
node(int _data = 0, node *_next = NULL) : data(_data), next(_next) { }
}Node, *PNode, LinkedList, *PLinkedList;
PLinkedList Merge(PLinkedList &A, PLinkedList &B)
{
PNode C = new Node( );
PNode last = C;
PNode p = A->next, q = B->next;
while(p && q)
{
if(p->data < q->data)
{
last->next = p;
last = p;
p = p->next;
}
else
{
last->next = q;
last = q;
q = q->next;
}
}
if(p) last->next = p;
if(q) last->next = q;
delete A;
A = NULL;
delete B;
B = NULL;
return C;
}