合并有序链表

using namespace std;  

  

  

struct ListNode  

{  

    int         m_Data;  

    ListNode*   m_pNext;  

    ListNode(int value,ListNode* next = NULL):m_Data(value),m_pNext(next){}  

};  

  

/* 

两个链表  比如链表1： 1->3->5->7->9 

            链表2：  2->4->6->8->10 

 

            跟我们合并两个数组一样，链表1的头结点  和链表2的头节点比较，如果链表1头节点的值大于链表2头接点的值， 

            那么链表2的头结点为合并链表的头结点，那么链表1的头节点继续和链表2的第二个节点（剩余链表2的头结点） 

            作比较，但一个链表遍历完之后，如果另外一个链表还没有遍历完，因为链表本来就是排序的，所以让合并链表的 

            尾巴节点指向未遍历完链表的头结点就可以 

 

            举个例子： 

 

            链表1： 1，3，5，23，34； 

            链表2： 2，4，6，8，10； 

            当遍历之后 链表3：1，2，3，4，8，10  此时链表2已经遍历完，while循环退出，但是剩余链表1还有 23，34 

            此时 让链表3的尾巴节点10 链接 剩余链表的头节点 23  就可以了 

*/  

  

ListNode* MergeList2(ListNode* head1,ListNode* head2)  

{  

    if (head1 == NULL)  

    {  

        return head2;  

    }  

    else if(head2 == NULL)  

    {  

        return head1;  

    }  

  

    ListNode* MergeHead = NULL;  

    if (head1->m_Data < head2->m_Data)  

    {  

        MergeHead = head1;  

        head1 = head1->m_pNext;  

    }  

    else  

    {  

        MergeHead = head2;  

        head2 = head2->m_pNext;  

    }  

    ListNode* tmpNode = MergeHead;  

    while (head1&&head2)  

    {  

        if (head1->m_Data < head2->m_Data)  

        {  

            MergeHead->m_pNext = head1;  

            head1 = head1->m_pNext;  

        }  

        else  

        {  

            MergeHead->m_pNext = head2;  

            head2 = head2->m_pNext;  

        }  

        MergeHead = MergeHead->m_pNext;  

    }  

    if (head1)  

    {  

        MergeHead->m_pNext = head1;  

    }  

    if (head2)  

    {  

        MergeHead->m_pNext = head2;  

    }  

  

    return tmpNode;  

  

}  

int _tmain(int argc, _TCHAR* argv[])  

{  

    ListNode* pHead1 = new ListNode(1);  

    ListNode* pCur = pHead1;  

    for (int i = 3; i < 10; i+=2)  

    {  

        ListNode* tmpNode = new ListNode(i);  

        pCur->m_pNext = tmpNode;  

        pCur = tmpNode;  

    }  

  

    ListNode* pHead2 = new ListNode(2);  

    pCur = pHead2;  

    for (int j = 4; j < 10; j+=2)  

    {  

        ListNode* tmpNode = new ListNode(j);  

        pCur->m_pNext = tmpNode;  

        pCur = tmpNode;  

    }  

  

    ListNode* head = MergeList2(pHead1,pHead2);  

    while (head)  

    {  

        cout<<head->m_Data<<" ";  

        head=head->m_pNext;  

    }  

  

  

    getchar();  

    return 0;  

}</span>