JZ-C-17

剑指offer第十七题：合并两个排序的链表
  1 //============================================================================
  2 // Name        : JZ-C-17.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description :合并两个排序的链表
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include <stdio.h>
 11 #include "List.h"
 12 using namespace std;
 13 ListNode* Merge(ListNode* pHead, ListNode* qHead) {
 14     if (pHead == NULL) { //考虑某链表为空的情况
 15         return qHead;
 16     } else if (qHead == NULL) {
 17         return pHead;
 18     }
 19     ListNode* NewHead = NULL;
 20     if (pHead->m_nValue < qHead->m_nValue) {
 21         NewHead = pHead;
 22         NewHead->m_pNext = Merge(pHead->m_pNext, qHead); //递归
 23     } else { //包含了相等的情况
 24         NewHead = qHead;
 25         NewHead->m_pNext = Merge(pHead, qHead->m_pNext);
 26     }
 27     return NewHead;
 28 }
 29 
 30 // ====================测试代码====================
 31 ListNode* Test(char* testName, ListNode* pHead1, ListNode* pHead2) {
 32     if (testName != NULL)
 33         printf("%s begins:
", testName);
 34 
 35     printf("The first list is:
");
 36     PrintList(pHead1);
 37 
 38     printf("The second list is:
");
 39     PrintList(pHead2);
 40 
 41     printf("The merged list is:
");
 42     ListNode* pMergedHead = Merge(pHead1, pHead2);
 43     PrintList(pMergedHead);
 44 
 45     printf("

");
 46 
 47     return pMergedHead;
 48 }
 49 
 50 // list1: 1->3->5
 51 // list2: 2->4->6
 52 void Test1() {
 53     ListNode* pNode1 = CreateListNode(1);
 54     ListNode* pNode3 = CreateListNode(3);
 55     ListNode* pNode5 = CreateListNode(5);
 56 
 57     ConnectListNodes(pNode1, pNode3);
 58     ConnectListNodes(pNode3, pNode5);
 59 
 60     ListNode* pNode2 = CreateListNode(2);
 61     ListNode* pNode4 = CreateListNode(4);
 62     ListNode* pNode6 = CreateListNode(6);
 63 
 64     ConnectListNodes(pNode2, pNode4);
 65     ConnectListNodes(pNode4, pNode6);
 66 
 67     ListNode* pMergedHead = Test("Test1", pNode1, pNode2);
 68 
 69     DestroyList(pMergedHead);
 70 }
 71 
 72 // 两个链表中有重复的数字
 73 // list1: 1->3->5
 74 // list2: 1->3->5
 75 void Test2() {
 76     ListNode* pNode1 = CreateListNode(1);
 77     ListNode* pNode3 = CreateListNode(3);
 78     ListNode* pNode5 = CreateListNode(5);
 79 
 80     ConnectListNodes(pNode1, pNode3);
 81     ConnectListNodes(pNode3, pNode5);
 82 
 83     ListNode* pNode2 = CreateListNode(1);
 84     ListNode* pNode4 = CreateListNode(3);
 85     ListNode* pNode6 = CreateListNode(5);
 86 
 87     ConnectListNodes(pNode2, pNode4);
 88     ConnectListNodes(pNode4, pNode6);
 89 
 90     ListNode* pMergedHead = Test("Test2", pNode1, pNode2);
 91 
 92     DestroyList(pMergedHead);
 93 }
 94 
 95 // 两个链表都只有一个数字
 96 // list1: 1
 97 // list2: 2
 98 void Test3() {
 99     ListNode* pNode1 = CreateListNode(1);
100     ListNode* pNode2 = CreateListNode(2);
101 
102     ListNode* pMergedHead = Test("Test3", pNode1, pNode2);
103 
104     DestroyList(pMergedHead);
105 }
106 
107 // 一个链表为空链表
108 // list1: 1->3->5
109 // list2: 空链表
110 void Test4() {
111     ListNode* pNode1 = CreateListNode(1);
112     ListNode* pNode3 = CreateListNode(3);
113     ListNode* pNode5 = CreateListNode(5);
114 
115     ConnectListNodes(pNode1, pNode3);
116     ConnectListNodes(pNode3, pNode5);
117 
118     ListNode* pMergedHead = Test("Test4", pNode1, NULL);
119 
120     DestroyList(pMergedHead);
121 }
122 
123 // 两个链表都为空链表
124 // list1: 空链表
125 // list2: 空链表
126 void Test5() {
127     ListNode* pMergedHead = Test("Test5", NULL, NULL);
128 }
129 
130 int main(int argc, char** argv) {
131     Test1();
132     Test2();
133     Test3();
134     Test4();
135     Test5();
136 
137     return 0;
138 }