方法一:递归 : 要注意递归结束的条件及代码的鲁棒性
方法二:非递归。需要较多的指针
1 #include<iostream>
2 #include<stdio.h>
3 #include<tchar.h>
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 ",pNode->m_nValue);
26 pNode = pNode->m_pNext;
27 }
28 printf("
");
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.
");
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 else
112 {
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->5
127 //list2: 2->4->6
128
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:
");
146 PrintList(pNode1);
147
148 printf("The second list is:
");
149 PrintList(pNode2);
150
151 printf("The merged list is:
");
152
153 //由于函数是会改变链表，不能同时运行。将true改变为false即可测试方法二
154 if(true)
155 {
156 printf("Solution1
");
157 ListNode* pMergedHead = Merge1(pNode1, pNode2);
158 PrintList(pMergedHead);
159 DestroyList(pMergedHead);
160 }
161 else
162 {
163 printf("Solution2
");
164 ListNode* pMergedHead = Merge2(pNode1, pNode2);
165 PrintList(pMergedHead);
166 DestroyList(pMergedHead);
167 }
168
169 }
