方法一:递归 : 要注意递归结束的条件及代码的鲁棒性
方法二:非递归。需要较多的指针
1 #include2 #include 3 #include 4 5 struct ListNode 6 { 7 int m_nValue; 8 ListNode* m_pNext; 9 }; 10 11 ListNode* CreateListNode(int value) 12 { 13 ListNode* pNode = new ListNode(); 14 pNode->m_nValue = value; 15 pNode->m_pNext = NULL; 16 17 return pNode; 18 } 19 20 void PrintList(ListNode* pHead) 21 { 22 ListNode* pNode = pHead; 23 while(pNode != NULL) 24 { 25 printf("%d\t",pNode->m_nValue); 26 pNode = pNode->m_pNext; 27 } 28 printf("\n"); 29 } 30 31 void DestroyList(ListNode* pHead) 32 { 33 ListNode* pNode = pHead; 34 while(pNode != NULL) 35 { 36 pHead = pHead->m_pNext; 37 delete pNode; 38 pNode = pHead; 39 } 40 } 41 42 void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) 43 { 44 if(pCurrent == NULL) 45 { 46 printf("Error to connect two nodes.\n"); 47 exit(1); 48 } 49 50 pCurrent->m_pNext = pNext; 51 } 52 53 //方法1 递归 要注意代码的鲁棒性 54 ListNode* Merge1(ListNode* pHead1, ListNode* pHead2) 55 { 56 if(pHead1 == NULL) 57 return pHead2; 58 else if(pHead2 == NULL) 59 return pHead1; 60 61 ListNode* pMergedHead = NULL; 62 63 if(pHead1->m_nValue < pHead2->m_nValue) 64 { 65 pMergedHead = pHead1; 66 pMergedHead->m_pNext = Merge1(pHead1->m_pNext, pHead2); 67 } 68 else 69 { 70 pMergedHead = pHead2; 71 pMergedHead->m_pNext = Merge1(pHead1, pHead2->m_pNext); 72 } 73 74 return pMergedHead; 75 } 76 77 //方法2: 非递归 比递归麻烦太多，定义的指针也多了一些。不过容易理解 78 ListNode* Merge2(ListNode* pHead1, ListNode* pHead2) 79 { 80 if(pHead1 == NULL) 81 return pHead2; 82 if(pHead2 == NULL) 83 return pHead1; 84 85 ListNode* pNode1 = pHead1; 86 ListNode* pNode2 = pHead2; 87 ListNode* pMergedHead = NULL; //合并后的链表的头结点 88 ListNode* pCurLastNode = NULL; 89 90 if(pNode1->m_nValue < pNode2->m_nValue) 91 { 92 pMergedHead = pHead1; 93 pNode1 = pNode1->m_pNext; 94 pCurLastNode = pMergedHead; 95 } 96 else 97 { 98 pMergedHead = pHead2; 99 pNode2 = pNode2->m_pNext;100 pCurLastNode = pMergedHead;101 }102 103 while(pNode1 !=NULL && pNode2 != NULL)104 {105 if(pNode1->m_nValue < pNode2->m_nValue)106 {107 pCurLastNode->m_pNext = pNode1;108 pCurLastNode = pNode1;109 pNode1 = pNode1->m_pNext;110 }111 else112 {113 pCurLastNode->m_pNext = pNode2;114 pCurLastNode = pNode2;115 pNode2 = pNode2->m_pNext; 116 }117 118 if(pNode1 == NULL)119 pCurLastNode->m_pNext = pNode2;120 if(pNode2 == NULL)121 pCurLastNode->m_pNext = pNode1;122 }123 return pMergedHead;124 }125 126 //list1: 1->3->5127 //list2: 2->4->6128 129 int main()130 {131 ListNode* pNode1 = CreateListNode(1);132 ListNode* pNode3 = CreateListNode(3);133 ListNode* pNode5 = CreateListNode(5);134 135 ConnectListNodes(pNode1, pNode3);136 ConnectListNodes(pNode3, pNode5);137 138 ListNode* pNode2 = CreateListNode(2);139 ListNode* pNode4 = CreateListNode(4);140 ListNode* pNode6 = CreateListNode(6);141 142 ConnectListNodes(pNode2, pNode4);143 ConnectListNodes(pNode4, pNode6);144 145 printf("The first list is:\n");146 PrintList(pNode1);147 148 printf("The second list is:\n");149 PrintList(pNode2);150 151 printf("The merged list is:\n");152 153 //由于函数是会改变链表，不能同时运行。将true改变为false即可测试方法二 154 if(true)155 {156 printf("Solution1\n");157 ListNode* pMergedHead = Merge1(pNode1, pNode2);158 PrintList(pMergedHead);159 DestroyList(pMergedHead);160 }161 else162 {163 printf("Solution2\n");164 ListNode* pMergedHead = Merge2(pNode1, pNode2);165 PrintList(pMergedHead);166 DestroyList(pMergedHead);167 }168 169 }
