探讨:将两个链表非降序合并为一个链表并依然有序的实现方法

// 

//将两个链表合并成一个链表，并且依然有序。方法保留了合并之前list1和list2的节点，
//合并之后list1和list2消失。将list1和list2合并为list3
template
void MergeList(MyList &list1, MyList &list2, MyList &list3)
{
 Node *head1 = list1.phead, *head2 = list2.phead;
 Node *head3 = list3.phead, *temp = NULL;
 if (head1->next == NULL)
 {//如果list1为空，则list3头指针指向list2
  head3 = head2;
  list2.phead->next = NULL;//将list2消除，防止析构函数析构list2时找不到对象
 }
 else if (head2->next == NULL)
 {//如果list1为空，则list3头指针指向list2
  head3 = head1;
  list1.phead->next = NULL;//将list1消除，防止析构函数析构list2时找不到对象
 }
 head1 = head1->next;
 list1.phead->next = NULL;//将list1消除，防止析构函数析构list2时找不到对象
 head2 = head2->next;
 list2.phead->next = NULL;//将list2消除，防止析构函数析构list2时找不到对象
 if (head1->data data)
 {//如果list1的第一个元素小于list2的第一个元素
  head3->next = head1;//将list1的第一个元素接到list3上
  head1 = head1->next;
 }
 else
 {
  head3->next = head2;//将list2的第一个元素接到list3上
  head2 = head2->next;
 }
 temp = head3->next;//指向list3当前最后一个节点
 while (head1 != NULL && head2 != NULL)
 {
  if (head1->data data)
  {
   temp->next = head1;//将list1中的元素接到list3的后面
   temp = head1;
   head1 = head1->next;
  }
  else
  {
   temp->next = head2;//将list2中的元素接到list3的后面
   temp = head2;
   head2 = head2->next;
  }
 }
 if (NULL == head1) //将list1或者list2中的剩余部分接到list3的后面
 {
  temp->next = head2;
 }
 else if (NULL == head2)
 {
  temp->next = head1;
 }
}
 
//主函数
int _tmain(int argc, _TCHAR* argv[])
{
 MyList list1, list2, list3;  
    for (int i = 1; i <= 10; i ++)  
    {  
       list1.Insert(i, 3*i);  
    list2.Insert(i, 2*i);
   }
   MergeList(list1, list2, list3);
 list3.Show();

 return 0;
}