//原来有序的两个链表合并之后依然有序

#include <iostream>

using namespace std;
typedef struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
}ListNode, *List;//必须是一个链表


void Insert(List& pHead,int data){
    ListNode* p=new ListNode;
    p->m_nValue=data;
    p->m_pNext=NULL;
    if(pHead==NULL)
        pHead=p;
    else{
        p->m_pNext=pHead;
        pHead=p;
    }

}
void Print(List& pHead){
    if(pHead==NULL)
        return ;
    ListNode* p=pHead;
    while(p){
        cout<<p->m_nValue<<" ";
        p=p->m_pNext;
    }
    cout<<endl;
}
List Merge(List& L1, List& L2){
    ListNode* p1=L1;
    ListNode* p2=L2;
    ListNode* pMergeHead=NULL;
    if(L1==NULL)
        return L2;
    else if(L2==NULL)
        return L1;
    if((p1->m_nValue) > (p2->m_nValue)){
        pMergeHead=p1;
        pMergeHead->m_pNext=Merge(p1->m_pNext,p2);
    }
    else{
        pMergeHead=p2;
        pMergeHead->m_pNext=Merge(p1,p2->m_pNext);
    }
    return pMergeHead;
}
int main()
{

    List L=NULL;
    List S=NULL;
    Insert(L,1);
    Insert(L,2);
    Insert(L,3);
    Insert(L,4);
    Print(L);
    Insert(S,2);
    Insert(S,3);
    Insert(S,4);
    Insert(S,5);
    Print(S);
    List tt=Merge(L,S);
    ListNode* p=tt;
    while(p){
        cout<<p->m_nValue<<" ";
        p=p->m_pNext;
    }
    return 0;
}

//还记得typedef struct and struct的区别吗？
下面的结果也是正确的  理解为ListNode *=List；

#include <iostream>

using namespace std;
struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};//必须是一个链表


void Insert(ListNode* &pHead,int data){
    ListNode* p=new ListNode;
    p->m_nValue=data;
    p->m_pNext=NULL;
    if(pHead==NULL)
        pHead=p;
    else{
        p->m_pNext=pHead;
        pHead=p;
    }

}
void Print(ListNode* &pHead){//ListNode* 链表，&pHead不会改变头结点
    if(pHead==NULL)
        return ;
    ListNode* p=pHead;
    while(p){
        cout<<p->m_nValue<<" ";
        p=p->m_pNext;
    }
    cout<<endl;
}
//ListNode* FindKthTotail(ListNode* pHead, int k){
//    if(pHead==NULL||k<=0)//非法输入
//        return NULL;
//    ListNode* p1=pHead, *p2=pHead;
//
//    for(int i=0;i<k-1;i++){
//        if(p1->m_pNext!=NULL){
//            p1=p1->m_pNext;//第一个指针走k-1步
//        }
//        else
//            return NULL;//长度不够k个节点
//     }
//
//
//    while(p1->m_pNext!=NULL){
//            p2=p2->m_pNext;
//            p1=p1->m_pNext;
//    }
//    return p2;
//}
//ListNode *ReverseList(List &L){
//    ListNode* pNode=L;
//    List ReverseHead=NULL;
//    ListNode* pPre=NULL;//前一个节点
//    while(pNode!=NULL){
//        ListNode* pNext=pNode->m_pNext;//保存后一个节点，不至于反转时候丢失
//
//        if(pNext==NULL)
//            ReverseHead=pNode;//就一个节点
//        pNode->m_pNext=pPre;//实现反转
//        pPre=pNode;
//        pNode=pNext;//继续下一对节点的反转
//    }
//    return ReverseHead;
//}
ListNode  *Merge(ListNode  *L1, ListNode  *L2){
    ListNode* p1=L1;
    ListNode* p2=L2;
    ListNode* pMergeHead=NULL;
    if(L1==NULL)
        return L2;
    else if(L2==NULL)
        return L1;
    if((p1->m_nValue) > (p2->m_nValue)){
        pMergeHead=p1;
        pMergeHead->m_pNext=Merge(p1->m_pNext,p2);
    }
    else{
        pMergeHead=p2;
        pMergeHead->m_pNext=Merge(p1,p2->m_pNext);
    }
    return pMergeHead;
}
int main()
{

    ListNode  *L=NULL;
    ListNode  *S=NULL;
    Insert(L,1);
    Insert(L,2);
    Insert(L,3);
    Insert(L,4);
    Print(L);
    Insert(S,2);
    Insert(S,3);
    Insert(S,4);
    Insert(S,5);
    Print(S);
    ListNode* p=Merge(L,S);
   // ListNode* p=tt;
    while(p){
        cout<<p->m_nValue<<" ";
        p=p->m_pNext;
    }
    return 0;
}