剑指offer——面试题25：合并两个排序的链表

自己答案：

 ListNode* MergeTwoSortedList(ListNode* pHead1,ListNode* pHead2)

 {

     if(pHead1==nullptr&&pHead2==nullptr)

         return nullptr;

     if(pHead1==nullptr)

         return pHead2;

     if(pHead2==nullptr)

         return pHead1;

     ListNode* pHead=(pHead1->m_Value<pHead2->m_Value)?pHead1:pHead2;

     ListNode* pNode1=pHead1;

     ListNode* pNode2=pHead2;

     while(pNode1!=nullptr&&pNode2!=nullptr)

     {

         ListNode* pNext1=pNode1->m_pNext;

         ListNode* pNext2=pNode2->m_pNext;

         if(pNode1->m_Value<pNode2->m_Value)

         {

             if((pNext1!=nullptr&&pNext1->m_Value>pNode2->m_Value)||pNext1==nullptr)

                 pNode1->m_pNext=pNode2;

             pNode1=pNext1;

         }

         else

         {

             if((pNext2!=nullptr&&pNext2->m_Value>pNode1->m_Value)||pNext2==nullptr)

                 pNode2->m_pNext=pNode1;

             pNode2=pNext2;

         }

     }

     return pHead;

 }

函数

#include"List.h"

void  Test(char* testName,ListNode* pHead,int* expect,int length)

{

    cout<<testName<<":";

    ListNode* pNode=pHead;

    int cnt=;

    while(pNode!=nullptr)

    {

        if(pNode->m_Value!=expect[cnt])

            break;

        pNode=pNode->m_pNext;

        cnt++;

    }

    if(cnt==length)

        cout<<"Passed."<<endl;

    else

        cout<<"Failed."<<endl;

}

void Test1()

{

    ListNode* pNode1_1=nullptr;

    ListNode* pNode2_1=nullptr;

    ListNode*  pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    Test("test1",pHead,nullptr,);

}

void Test2()

{

    ListNode* pNode1_1=nullptr;

    ListNode* pNode2_1=CreateListNode();

    ListNode* pNode2_2=CreateListNode();

    ConnectListNodes(pNode2_1,pNode2_2);

    ListNode*  pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,};

    Test("test2",pHead,data,);

}

void Test3()

{

    ListNode* pNode2_1=nullptr;

    ListNode* pNode1_1=CreateListNode();

    ListNode* pNode1_2=CreateListNode();

    ConnectListNodes(pNode1_1,pNode1_2);

    ListNode*  pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,};

    Test("test3",pHead,data,);

}

void Test4()

{

    ListNode* pNode2_1=CreateListNode();

    ListNode* pNode1_1=CreateListNode();

    ListNode* pNode1_2=CreateListNode();

    ConnectListNodes(pNode1_1,pNode1_2);

    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,,};

    Test("test4",pHead,data,);

}

void Test5()

{

    ListNode* pNode2_1=CreateListNode();

    ListNode* pNode1_1=CreateListNode();

    ListNode* pNode1_2=CreateListNode();

    ConnectListNodes(pNode1_1,pNode1_2);

    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,,};

    Test("test4",pHead,data,);

}

void Test6()

{

    ListNode* pNode2_1=CreateListNode();

    ListNode* pNode2_2=CreateListNode();

    ListNode* pNode2_3=CreateListNode();

    ConnectListNodes(pNode2_1,pNode2_2);

    ConnectListNodes(pNode2_2,pNode2_3);

    ListNode* pNode1_1=CreateListNode();

    ListNode* pNode1_2=CreateListNode();

    ListNode* pNode1_3=CreateListNode();

    ConnectListNodes(pNode1_1,pNode1_2);

    ConnectListNodes(pNode1_2,pNode1_3);

    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,,,,,};

    Test("test6",pHead,data,);

}

void Test7()

{

    ListNode* pNode2_1=CreateListNode();

    ListNode* pNode2_2=CreateListNode();

    ListNode* pNode2_3=CreateListNode();

    ConnectListNodes(pNode2_1,pNode2_2);

    ConnectListNodes(pNode2_2,pNode2_3);

    ListNode* pNode1_1=CreateListNode();

    ListNode* pNode1_2=CreateListNode();

    ListNode* pNode1_3=CreateListNode();

    ConnectListNodes(pNode1_1,pNode1_2);

    ConnectListNodes(pNode1_2,pNode1_3);

    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);

    int data[]={,,,,,};

    Test("test7",pHead,data,);

}

int main()

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    Test7();

    return ;

}

测试代码

官方答案：

 ListNode* MergeTwoSortedListWihtRecursive(ListNode* pHead1,ListNode* pHead2)

 {

     if(pHead1==nullptr || pHead2==nullptr)

     {

         return nullptr;

     }

     if(pHead1==nullptr)

     {

         return pHead2;

     }

     if(pHead2==nullptr)

     {

         return pHead1;

     }

     ListNode* pHead=nullptr;

     if(pHead1->m_Value<pHead2->m_Value)

     {

         pHead=pHead1;

         pHead->m_pNext=MergeTwoSortedListWihtRecursive(pHead1->m_pNext,pHead2);

     }

     else

     {

         pHead=pHead2;

         pHead->m_pNext=MergeTwoSortedListWihtRecursive(pHead1,pHead2->m_pNext);

     }

     return pHead;

 }

函数(递归)

 // 面试题25：合并两个排序的链表

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

 // 照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链

 // 表3所示。

 #include <cstdio>

 #include "..\Utilities\List.h"

 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)

 {

     if(pHead1 == nullptr)

         return pHead2;

     else if(pHead2 == nullptr)

         return pHead1;

     ListNode* pMergedHead = nullptr;

     if(pHead1->m_nValue < pHead2->m_nValue)

     {

         pMergedHead = pHead1;

         pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);

     }

     else

     {

         pMergedHead = pHead2;

         pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);

     }

     return pMergedHead;

 }

 // ====================测试代码====================

 ListNode* Test(char* testName, ListNode* pHead1, ListNode* pHead2)

 {

     if(testName != nullptr)

         printf("%s begins:\n", testName);

     printf("The first list is:\n");

     PrintList(pHead1);

     printf("The second list is:\n");

     PrintList(pHead2);

     printf("The merged list is:\n");

     ListNode* pMergedHead = Merge(pHead1, pHead2);

     PrintList(pMergedHead);

     printf("\n\n");

     return pMergedHead;

 }

 // list1: 1->3->5

 // list2: 2->4->6

 void Test1()

 {

     ListNode* pNode1 = CreateListNode();

     ListNode* pNode3 = CreateListNode();

     ListNode* pNode5 = CreateListNode();

     ConnectListNodes(pNode1, pNode3);

     ConnectListNodes(pNode3, pNode5);

     ListNode* pNode2 = CreateListNode();

     ListNode* pNode4 = CreateListNode();

     ListNode* pNode6 = CreateListNode();

     ConnectListNodes(pNode2, pNode4);

     ConnectListNodes(pNode4, pNode6);

     ListNode* pMergedHead = Test("Test1", pNode1, pNode2);

     DestroyList(pMergedHead);

 }

 // 两个链表中有重复的数字

 // list1: 1->3->5

 // list2: 1->3->5

 void Test2()

 {

     ListNode* pNode1 = CreateListNode();

     ListNode* pNode3 = CreateListNode();

     ListNode* pNode5 = CreateListNode();

     ConnectListNodes(pNode1, pNode3);

     ConnectListNodes(pNode3, pNode5);

     ListNode* pNode2 = CreateListNode();

     ListNode* pNode4 = CreateListNode();

     ListNode* pNode6 = CreateListNode();

     ConnectListNodes(pNode2, pNode4);

     ConnectListNodes(pNode4, pNode6);

     ListNode* pMergedHead = Test("Test2", pNode1, pNode2);

     DestroyList(pMergedHead);

 }

 // 两个链表都只有一个数字

 // list1: 1

 // list2: 2

 void Test3()

 {

     ListNode* pNode1 = CreateListNode();

     ListNode* pNode2 = CreateListNode();

     ListNode* pMergedHead = Test("Test3", pNode1, pNode2);

     DestroyList(pMergedHead);

 }

 // 一个链表为空链表

 // list1: 1->3->5

 // list2: 空链表

 void Test4()

 {

     ListNode* pNode1 = CreateListNode();

     ListNode* pNode3 = CreateListNode();

     ListNode* pNode5 = CreateListNode();

     ConnectListNodes(pNode1, pNode3);

     ConnectListNodes(pNode3, pNode5);

     ListNode* pMergedHead = Test("Test4", pNode1, nullptr);

     DestroyList(pMergedHead);

 }

 // 两个链表都为空链表

 // list1: 空链表

 // list2: 空链表

 void Test5()

 {

     ListNode* pMergedHead = Test("Test5", nullptr, nullptr);

 }

 int main(int argc, char* argv[])

 {

     Test1();

     Test2();

     Test3();

     Test4();

     Test5();

     return ;

 }

测试代码

巴特西

剑指offer——面试题25：合并两个排序的链表

最新文章

热门文章

巴特西

剑指offer——面试题25：合并两个 排序的链表

最新文章

热门文章

剑指offer——面试题25：合并两个排序的链表