当前位置：首页 > news >正文

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

news 来源：原创 2024/4/25 9:52:07

自己答案：

 1 ListNode* MergeTwoSortedList(ListNode* pHead1,ListNode* pHead2)
 2 {
 3     if(pHead1==nullptr&&pHead2==nullptr)
 4         return nullptr;
 5 
 6     if(pHead1==nullptr)
 7         return pHead2;
 8 
 9     if(pHead2==nullptr)
10         return pHead1;
11 
12     ListNode* pHead=(pHead1->m_Value<pHead2->m_Value)?pHead1:pHead2;
13 
14     ListNode* pNode1=pHead1;
15     ListNode* pNode2=pHead2;
16     while(pNode1!=nullptr&&pNode2!=nullptr)
17     {
18         ListNode* pNext1=pNode1->m_pNext;
19         ListNode* pNext2=pNode2->m_pNext;
20 
21         if(pNode1->m_Value<pNode2->m_Value)
22         {
23             if((pNext1!=nullptr&&pNext1->m_Value>pNode2->m_Value)||pNext1==nullptr)
24                 pNode1->m_pNext=pNode2;
25             pNode1=pNext1;
26         }
27         else
28         {
29             if((pNext2!=nullptr&&pNext2->m_Value>pNode1->m_Value)||pNext2==nullptr)
30                 pNode2->m_pNext=pNode1;
31             pNode2=pNext2;
32         }
33     }
34     return pHead;
35 }

函数

#include"List.h"

void  Test(char* testName,ListNode* pHead,int* expect,int length)
{
    cout<<testName<<":";
    ListNode* pNode=pHead;
    int cnt=0;
    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,0);
}

void Test2()
{
    ListNode* pNode1_1=nullptr;
    ListNode* pNode2_1=CreateListNode(1);
    ListNode* pNode2_2=CreateListNode(2);
    ConnectListNodes(pNode2_1,pNode2_2);
    ListNode*  pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[2]={1,2};
    Test("test2",pHead,data,2);
}

void Test3()
{
    ListNode* pNode2_1=nullptr;
    ListNode* pNode1_1=CreateListNode(1);
    ListNode* pNode1_2=CreateListNode(2);
    ConnectListNodes(pNode1_1,pNode1_2);
    ListNode*  pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[2]={1,2};
    Test("test3",pHead,data,2);
}

void Test4()
{
    ListNode* pNode2_1=CreateListNode(1);
    ListNode* pNode1_1=CreateListNode(1);
    ListNode* pNode1_2=CreateListNode(2);
    ConnectListNodes(pNode1_1,pNode1_2);
    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[3]={1,1,2};
    Test("test4",pHead,data,3);
}

void Test5()
{
    ListNode* pNode2_1=CreateListNode(3);
    ListNode* pNode1_1=CreateListNode(1);
    ListNode* pNode1_2=CreateListNode(2);
    ConnectListNodes(pNode1_1,pNode1_2);
    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[3]={1,2,3};
    Test("test4",pHead,data,3);
}

void Test6()
{
    ListNode* pNode2_1=CreateListNode(2);
    ListNode* pNode2_2=CreateListNode(4);
    ListNode* pNode2_3=CreateListNode(6);
    ConnectListNodes(pNode2_1,pNode2_2);
    ConnectListNodes(pNode2_2,pNode2_3);

    ListNode* pNode1_1=CreateListNode(1);
    ListNode* pNode1_2=CreateListNode(3);
    ListNode* pNode1_3=CreateListNode(5);
    ConnectListNodes(pNode1_1,pNode1_2);
    ConnectListNodes(pNode1_2,pNode1_3);
    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[6]={1,2,3,4,5,6};
    Test("test6",pHead,data,6);
}

void Test7()
{
    ListNode* pNode2_1=CreateListNode(3);
    ListNode* pNode2_2=CreateListNode(4);
    ListNode* pNode2_3=CreateListNode(6);
    ConnectListNodes(pNode2_1,pNode2_2);
    ConnectListNodes(pNode2_2,pNode2_3);

    ListNode* pNode1_1=CreateListNode(1);
    ListNode* pNode1_2=CreateListNode(2);
    ListNode* pNode1_3=CreateListNode(7);
    ConnectListNodes(pNode1_1,pNode1_2);
    ConnectListNodes(pNode1_2,pNode1_3);
    ListNode* pHead=MergeTwoSortedList(pNode1_1,pNode2_1);
    int data[6]={1,2,3,4,6,7};
    Test("test7",pHead,data,6);
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();

    return 0;
}

测试代码

官方答案：

 1 ListNode* MergeTwoSortedListWihtRecursive(ListNode* pHead1,ListNode* pHead2)
 2 {
 3     if(pHead1==nullptr || pHead2==nullptr)
 4     {
 5         return nullptr;
 6     }
 7     if(pHead1==nullptr)
 8     {
 9         return pHead2;
10     }
11     if(pHead2==nullptr)
12     {
13         return pHead1;
14     }
15     
16     ListNode* pHead=nullptr;
17     
18     if(pHead1->m_Value<pHead2->m_Value)
19     {
20         pHead=pHead1;
21         pHead->m_pNext=MergeTwoSortedListWihtRecursive(pHead1->m_pNext,pHead2);
22     }
23     else
24     {
25         pHead=pHead2;
26         pHead->m_pNext=MergeTwoSortedListWihtRecursive(pHead1,pHead2->m_pNext);
27     }
28     return pHead;
29 }

函数(递归)

  1 // 面试题25：合并两个排序的链表
  2 // 题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按
  3 // 照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链
  4 // 表3所示。
  5 
  6 #include <cstdio>
  7 #include "..\Utilities\List.h"
  8 
  9 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 10 {
 11     if(pHead1 == nullptr)
 12         return pHead2;
 13     else if(pHead2 == nullptr)
 14         return pHead1;
 15 
 16     ListNode* pMergedHead = nullptr;
 17 
 18     if(pHead1->m_nValue < pHead2->m_nValue)
 19     {
 20         pMergedHead = pHead1;
 21         pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
 22     }
 23     else
 24     {
 25         pMergedHead = pHead2;
 26         pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
 27     }
 28 
 29     return pMergedHead;
 30 }
 31 
 32 // ====================测试代码====================
 33 ListNode* Test(char* testName, ListNode* pHead1, ListNode* pHead2)
 34 {
 35     if(testName != nullptr)
 36         printf("%s begins:\n", testName);
 37 
 38     printf("The first list is:\n");
 39     PrintList(pHead1);
 40 
 41     printf("The second list is:\n");
 42     PrintList(pHead2);
 43 
 44     printf("The merged list is:\n");
 45     ListNode* pMergedHead = Merge(pHead1, pHead2);
 46     PrintList(pMergedHead);
 47     
 48     printf("\n\n");
 49 
 50     return pMergedHead;
 51 }
 52 
 53 // list1: 1->3->5
 54 // list2: 2->4->6
 55 void Test1()
 56 {
 57     ListNode* pNode1 = CreateListNode(1);
 58     ListNode* pNode3 = CreateListNode(3);
 59     ListNode* pNode5 = CreateListNode(5);
 60 
 61     ConnectListNodes(pNode1, pNode3);
 62     ConnectListNodes(pNode3, pNode5);
 63 
 64     ListNode* pNode2 = CreateListNode(2);
 65     ListNode* pNode4 = CreateListNode(4);
 66     ListNode* pNode6 = CreateListNode(6);
 67 
 68     ConnectListNodes(pNode2, pNode4);
 69     ConnectListNodes(pNode4, pNode6);
 70 
 71     ListNode* pMergedHead = Test("Test1", pNode1, pNode2);
 72 
 73     DestroyList(pMergedHead);
 74 }
 75 
 76 // 两个链表中有重复的数字
 77 // list1: 1->3->5
 78 // list2: 1->3->5
 79 void Test2()
 80 {
 81     ListNode* pNode1 = CreateListNode(1);
 82     ListNode* pNode3 = CreateListNode(3);
 83     ListNode* pNode5 = CreateListNode(5);
 84 
 85     ConnectListNodes(pNode1, pNode3);
 86     ConnectListNodes(pNode3, pNode5);
 87 
 88     ListNode* pNode2 = CreateListNode(1);
 89     ListNode* pNode4 = CreateListNode(3);
 90     ListNode* pNode6 = CreateListNode(5);
 91 
 92     ConnectListNodes(pNode2, pNode4);
 93     ConnectListNodes(pNode4, pNode6);
 94 
 95     ListNode* pMergedHead = Test("Test2", pNode1, pNode2);
 96 
 97     DestroyList(pMergedHead);
 98 }
 99 
100 // 两个链表都只有一个数字
101 // list1: 1
102 // list2: 2
103 void Test3()
104 {
105     ListNode* pNode1 = CreateListNode(1);
106     ListNode* pNode2 = CreateListNode(2);
107 
108     ListNode* pMergedHead = Test("Test3", pNode1, pNode2);
109 
110     DestroyList(pMergedHead);
111 }
112 
113 // 一个链表为空链表
114 // list1: 1->3->5
115 // list2: 空链表
116 void Test4()
117 {
118     ListNode* pNode1 = CreateListNode(1);
119     ListNode* pNode3 = CreateListNode(3);
120     ListNode* pNode5 = CreateListNode(5);
121 
122     ConnectListNodes(pNode1, pNode3);
123     ConnectListNodes(pNode3, pNode5);
124 
125     ListNode* pMergedHead = Test("Test4", pNode1, nullptr);
126 
127     DestroyList(pMergedHead);
128 }
129 
130 // 两个链表都为空链表
131 // list1: 空链表
132 // list2: 空链表
133 void Test5()
134 {
135     ListNode* pMergedHead = Test("Test5", nullptr, nullptr);
136 }
137 
138 int main(int argc, char* argv[])
139 {
140     Test1();
141     Test2();
142     Test3();
143     Test4();
144     Test5();
145 
146     return 0;
147 }