有序表的合并

1、问题描述:

个递增有序的单链表，请你把它两个合并成一个有序的单链表

2、数据结构设计

struct node

{

int value;

node* next;

};

3、算法设计

（1）给单链表添加节点

void insertNode(node* head, int value)

{

node* p = head->next;

if ( p == NULL )

{

   p = new node;

   p->value = value;

   p->next = NULL;

   head->next = p;

   return;

}

while ( p->next != NULL )

{

   p = p->next;

}

node* tmp = new node;

tmp->value = value;

tmp->next = NULL;

p->next = tmp;

}

（2）遍历输出链表节点

void print(node* head)

{

node* p = head->next;

while ( p != NULL )

{

   cout << p->value << " ";

   p = p->next;

}

cout << endl;

}

（3）合并有序表

node* formalMerge(node* headA, node* headB)

{

node* head = new node;

head->next = NULL;

node* p = headA->next;

node* q = headB->next;

if ( p == NULL )

{

   return headB;

}

if ( q == NULL )

{

   return headA;

}

while ( (p != NULL) && (q != NULL) )

{

   if ( p->value == q->value )

   {

    insertNode(head, p->value);

    insertNode(head, q->value);

    p = p->next;

    q = q->next;

   }

   else if ( p->value < q->value )

   {

    insertNode(head, p->value);

    p = p->next;

   }

   else if ( p->value > q->value )

   {

    insertNode(head, q->value);

    q = q->next;

   }

}

while ( p != NULL )

{

   insertNode(head, p->value);

   p = p->next;

}

while ( q != NULL )

{

   insertNode(head, q->value);

   q = q->next;

}

return head;

}

四、运行与测试