合并两个有序链表的算法

此算法的时间复杂度O(n),空间复杂度O(1).

#include<iostream>
/**
 *合并两个有序单链表的算法 
 *算法时间复杂度o(n+m):n为第一个有序单链表的长度，m是第二个有序单链表的长度 
 *空间复杂度o(1) 
 *
*/
using namespace std;
struct LNode{
       int data;
       LNode *next;
       LNode()
       {
              next = NULL;
       }
};

/**
 *思想该表指针的指向 
*/ 
LNode* merge(LNode*&list1,LNode*&list2)
{
       LNode*list=NULL;
       LNode* tmp = NULL;
       if(list1->data <= list2->data)
       {
               list=list1;
               list1=list1->next;
       }
       else
       {
               list = list2;
               list2=list2->next;
       }
       tmp = list;
       //list->next=NULL;  
       
       while(list1 != NULL && list2 != NULL)
       {
               if(list1->data <= list2->data)
               {
                 list->next=list1;
                 list1=list1->next;
               }
               else
               {
                 list->next = list2;
                 list2=list2->next;
               }
               //cout << "~"<< list->next->data<<endl;
               list = list->next;  
             //  list->next =NULL;        
       }
       /*
       while(list1!=NULL)
       {
         list = list1;
         list = list->next;
         list1 = list1->next;
       }
       while(list2!=NULL)
       {
         list = list2;
         list = list->next;
         list2 = list2->next;
       }*/
       return tmp;
}
int main()
{   LNode *list1 = new LNode;
    LNode *list2 = new LNode;
    
    /************初始化数据**************/
    LNode* tmp1 = list1;
    LNode*tmp = NULL;
    tmp1->data=2;
    
    tmp = new LNode;
    tmp->data=4;
    tmp1->next = tmp;
    tmp1 = tmp1->next;
    tmp = new LNode;
    tmp->data = 5;
    tmp1->next=tmp;
    tmp1 = tmp1->next;
    tmp = new LNode;
    tmp->data = 7;
    tmp1->next = tmp;

    LNode* tmp2 = list2;
    tmp2->data=1;
    
    tmp = new LNode;
    tmp->data=3;
    tmp2->next = tmp;
    
    tmp2 = tmp2->next;
    tmp = new LNode;
    tmp->data = 6;
    tmp2->next=tmp;
    /************end**************/
    tmp1 = list1;
    tmp2 =list2;
    while(tmp1 !=NULL)
    {
      cout << tmp1->data<< " ";
      tmp1 = tmp1->next;
    }
    cout << endl;
    while(tmp2!=NULL)
    {
      cout << tmp2->data<< " ";
      tmp2 = tmp2->next;
    }
    cout << endl;
    
    LNode*list=merge(list1,list2);
    while(list!=NULL)
    {
      cout << list->data<< " ";
      list = list->next;
    }
    cout << endl;
    system("pause");
    return 0;
}