合並兩個排序的鏈表，合並兩個排序

合並兩個排序的鏈表，合並兩個排序

題目：輸入兩個遞增排序的鏈表，合並這兩個鏈表並使新鏈表中的結點仍然是按照遞增排序的。

方法一:遞歸 : 要注意遞歸結束的條件及代碼的魯棒性

方法二:非遞歸。需要較多的指針

  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\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         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:\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     else
162     {
163         printf("Solution2\n");
164         ListNode* pMergedHead = Merge2(pNode1, pNode2);
165         PrintList(pMergedHead);
166         DestroyList(pMergedHead);
167     }
168     
169 }