剑指offer—第三章高质量代码（合并两个排序链表）

题目：输入员两个递增排序的链表，合并这两个链表并使新的链表中的结点仍然是按照递增排序的。

思路：首先，定义两个头节点分别为Head1和Head2的链表，然后比较第一个节点的值，如果是Head1->mValue比Head2->mValue小，那么头节点，就是Head1，递归实现后面的节点的排序。

C++代码：

#include<iostream>
using namespace std;
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};
ListNode* CreateList(int a[],int b)
{

    ListNode* pHead=NULL,*pNode=NULL;
    for(int i=0;i<b;i++)
    {
        ListNode* pNew=new ListNode();
        pNew->m_nValue=a[i];
        pNew->m_pNext=NULL;
        if(pHead==NULL)
        {
            pHead=pNew;
            pNode=pNew;
            
        }
        else
        {
            pNode->m_pNext=pNew;
            pNode=pNode->m_pNext;
        }
    }
    return pHead;
}
void PrintList(ListNode* pHead)
{
    if(pHead==NULL)
    {
        return;
    }
    ListNode* pNode=pHead;
    while(pNode!=NULL)
    {
        cout<<pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;

    }
    cout<<endl;
}
ListNode* MergeLink(ListNode* Head1,ListNode* Head2)
{
    ListNode* MergeHead=NULL;
    if(Head1==NULL)
        return Head2;
    if(Head2==NULL)
        return Head1;
    if(Head1==NULL&&Head2==NULL)
        return NULL;
    if(Head1->m_nValue>Head2->m_nValue)
    {
        MergeHead=Head2;
        Head2->m_pNext=MergeLink(Head2->m_pNext,Head1);
    }
    else
    {
        MergeHead=Head1;
        Head1->m_pNext=MergeLink(Head1->m_pNext,Head2);
    }
    return MergeHead;
}
void main()
{
    int a[]={3,4,5,6,8};
    int b[]={1,2,7};
    ListNode* Head1=CreateList(a,5);
    ListNode* Head2=CreateList(b,3);
    PrintList(Head1);
    PrintList(Head2);
    ListNode* Head3=MergeLink(Head1,Head2);
    PrintList(Head3);
    
}

Java代码：

public class MergeLink {

    public static class ListNode
    {
        int m_nValue;
        ListNode m_pNext;
    };
    public static ListNode CreateList(int[] a,int b)
    {

        ListNode pHead=null,pNode=null;
        for(int i=0;i<b;i++)
        {
            ListNode pNew=new ListNode();
            pNew.m_nValue=a[i];
            pNew.m_pNext=null;
            if(pHead==null)
            {
                pHead=pNew;
                pNode=pNew;
                
            }
            else
            {
                pNode.m_pNext=pNew;
                pNode=pNode.m_pNext;
            }
        }
        return pHead;
    }
    public static void PrintList(ListNode pHead)
    {
        if(pHead==null)
        {
            return;
        }
        ListNode pNode=pHead;
        while(pNode!=null)
        {
            
            System.out.print(pNode.m_nValue+" ");
            pNode=pNode.m_pNext;

        }
        System.out.println();
    }
    public static ListNode MergeLink(ListNode Head1,ListNode Head2)
    {
        ListNode MergeHead=null;
        if(Head1==null)
            return Head2;
        if(Head2==null)
            return Head1;
        if(Head1==null&&Head2==null)
            return null;
        if(Head1.m_nValue>Head2.m_nValue)
        {
            MergeHead=Head2;
            Head2.m_pNext=MergeLink(Head2.m_pNext,Head1);
        }
        else
        {
            MergeHead=Head1;
            Head1.m_pNext=MergeLink(Head1.m_pNext,Head2);
        }
        return MergeHead;
    }
    public static void main(String[] args)
    {
        int a[]={3,4,5,6,8};
        int b[]={1,2,7};
        ListNode Head1=CreateList(a,5);
        ListNode Head2=CreateList(b,3);
        PrintList(Head1);
        PrintList(Head2);
        ListNode Head3=MergeLink(Head1,Head2);
        PrintList(Head3);
        
    }

}