输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
struct ListNode { int m_nValue; ListNode* m_pNext; }; ListNode* Merge(ListNode* pHead1,ListNode* pHead2) { if(pHead1 == NULL) return pHead2; else if(pHead2 == NULL) return pHead1; ListNode *pMergeHead = NULL; if(pHead1->m_nValue < pHead2->m_nValue) { pMergeHead = pHead1; pMergeHead->m_pNext = Merge(pHead1->m_pNext,pHead2); } else { pMergeHead = pHead2; pMergeHead->m_pNext = Merge(pHead1,pHead2->m_pNext); } return pMergeHead; } ListNode* CreateListNode(int value) { ListNode* pNode = new ListNode(); pNode->m_nValue = value; pNode->m_pNext = NULL; return pNode; } void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) { if(pCurrent == NULL) { printf("Error to connect two nodes.\n"); } pCurrent->m_pNext = pNext; } void PrintListNode(ListNode* pNode) { if(pNode == NULL) { printf("The node is NULL\n"); } else { printf("The key in node is %d.\n", pNode->m_nValue); } } void PrintList(ListNode* pHead) { printf("PrintList starts.\n"); ListNode* pNode = pHead; while(pNode != NULL) { printf("%d\t", pNode->m_nValue); pNode = pNode->m_pNext; } printf("\nPrintList ends.\n"); } void DestroyList(ListNode* pHead) { ListNode* pNode = pHead; while(pNode != NULL) { pHead = pHead->m_pNext; delete pNode; pNode = pHead; } } ListNode* Test(char* testName, ListNode* pHead1, ListNode* pHead2) { if(testName != NULL) 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; } void Test1() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode3 = CreateListNode(3); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode3); ConnectListNodes(pNode3, pNode5); ListNode* pNode2 = CreateListNode(2); ListNode* pNode4 = CreateListNode(4); ListNode* pNode6 = CreateListNode(6); ConnectListNodes(pNode2, pNode4); ConnectListNodes(pNode4, pNode6); ListNode* pMergedHead = Test("Test1", pNode1, pNode2); DestroyList(pMergedHead); } void Test2() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode3 = CreateListNode(3); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode3); ConnectListNodes(pNode3, pNode5); ListNode* pNode2 = CreateListNode(1); ListNode* pNode4 = CreateListNode(3); ListNode* pNode6 = CreateListNode(5); ConnectListNodes(pNode2, pNode4); ConnectListNodes(pNode4, pNode6); ListNode* pMergedHead = Test("Test2", pNode1, pNode2); DestroyList(pMergedHead); } void Test3() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pMergedHead = Test("Test3", pNode1, pNode2); DestroyList(pMergedHead); } void Test4() { ListNode* pNode1 = CreateListNode(1); ListNode* pNode3 = CreateListNode(3); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode3); ConnectListNodes(pNode3, pNode5); ListNode* pMergedHead = Test("Test4", pNode1, NULL); DestroyList(pMergedHead); } void Test5() { ListNode* pMergedHead = Test("Test5", NULL, NULL); } int main() { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; }
