自己答案：
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 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 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 else28 {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< <<":"; 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."< 官方答案：
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 m_Value)19 {20 pHead=pHead1;21 pHead->m_pNext=MergeTwoSortedListWihtRecursive(pHead1->m_pNext,pHead2);22 }23 else24 {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 #include7 #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: 1102 // list2: 2103 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->5115 // 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 }