題目

????????有一個鏈表，其節點聲明如下：

struct TNode
{int nData;struct TNode *pNext;TNode(int x) : nData(x), pNext(NULL) {}
};

????????現給定兩個按升序排列的單鏈表pA和pB，請編寫一個函數，實現這兩個單鏈表的合并。合并后，仍然按升序進行排列。比如：單鏈表pA為1->3->5->6->8，單鏈表pB為2->3->7，則合并后返回的鏈表為1->2->3->3->5->6->7->8。函數的聲明如下：

??????????TNode *MergeList(TNode *pA, TNode *pB);

解析

????????這道題主要考察應聘者對鏈表等數據結構的理解能力，在面試中比較常見。一般有兩種解法：一種是使用遞歸函數來實現，另一種是使用鏈表遍歷來實現。

????????先來看第一種解法，使用遞歸函數來實現。當鏈表pA為NULL時，直接返回鏈表pB即可。當鏈表pB為NULL時，直接返回鏈表pA即可。當鏈表pA和pB均不為NULL時，則比較鏈表首部的元素，若pA->nData小于pB->nData，則返回pA，并讓pA->pNext指向遞歸函數MergeList(pA->pNext, pB)的返回值。下面，我們給出了這道題的示例代碼。

#include<iostream>
using namespace std;struct TNode
{int nData;struct TNode *pNext;TNode(int x) : nData(x), pNext(NULL) {}
};// 插入新節點到鏈表尾部
TNode *AppendNode(TNode *pTail, int nData)
{  TNode *pNodeNew = new TNode(nData);pTail->pNext = pNodeNew;return pNodeNew;
}// 打印鏈表
void PrintList(TNode *pNode)
{while (pNode != NULL){cout << pNode->nData;pNode = pNode->pNext;if (pNode != NULL){cout << "->";}else{cout << endl;}}
}// 合并兩個鏈表
TNode *MergeList(TNode *pA, TNode *pB)
{  if (pA == NULL){return pB;}if (pB == NULL){return pA;}if (pA->nData < pB->nData){pA->pNext = MergeList(pA->pNext, pB);return pA;}else{pB->pNext = MergeList(pA, pB->pNext);return pB;}
}  int main()
{TNode *pA = new TNode(1);TNode *pTail = AppendNode(pA, 3);pTail = AppendNode(pTail, 5);pTail = AppendNode(pTail, 6);pTail = AppendNode(pTail, 8);// 輸出：1->3->5->6->8PrintList(pA);TNode *pB = new TNode(2);pTail = AppendNode(pB, 3);pTail = AppendNode(pTail, 7);// 輸出：2->3->7PrintList(pB);TNode *pResult = MergeList(pA, pB);// 輸出：1->2->3->3->5->6->7->8PrintList(pResult);return 0;
}

????????當然，遞歸函數也有其缺點：當鏈表中的元素較多，遞歸的層級較多時，可能會導致堆棧溢出。

????????接下來，我們來看第二種解法，使用鏈表遍歷來實現。首先，當鏈表pA和pB其中一個為NULL時，直接返回另一個鏈表即可。接下來，我們創建了一個新的臨時節點，作為新鏈表的頭和尾，并遍歷鏈表pA和pB。在遍歷過程中，如果pA->nData小于pB->nData，則將pA作為新鏈表尾部的下一個節點，并遍歷新鏈表尾部和pA的下一個節點；如果pA->nData不小于pB->nData，則將pB作為新鏈表尾部的下一個節點，并遍歷新鏈表尾部和pB的下一個節點。循環遍歷完成后，由于鏈表pA和pB不一樣長，因此，需要檢查鏈表pA和pB是否為NULL。若不為NULL，則將對應鏈表放到新鏈表尾部。最后，我們返回了新建節點的下一個節點作為合并后的鏈表首節點，并刪除了新建的臨時節點。具體實現，可參考如下的示例代碼。

#include<iostream>
using namespace std;struct TNode
{int nData;struct TNode *pNext;TNode(int x) : nData(x), pNext(NULL) {}
};// 插入新節點到鏈表尾部
TNode *AppendNode(TNode *pTail, int nData)
{  TNode *pNodeNew = new TNode(nData);pTail->pNext = pNodeNew;return pNodeNew;
}// 打印鏈表
void PrintList(TNode *pNode)
{while (pNode != NULL){cout << pNode->nData;pNode = pNode->pNext;if (pNode != NULL){cout << "->";}else{cout << endl;}}
}// 合并兩個鏈表
TNode *MergeList(TNode *pA, TNode *pB)
{if (pA == NULL){return pB;}if (pB == NULL){return pA;}TNode *pResult = new TNode(-1);TNode *pTail = pResult;while (pA && pB){if (pA->nData < pB->nData){pTail->pNext = pA;pTail = pTail->pNext;pA = pA->pNext;} else{pTail->pNext = pB;pTail = pTail->pNext;pB = pB->pNext;}}if (pA){pTail->pNext = pA;}if (pB){pTail->pNext = pB;}TNode *pTemp = pResult;pResult = pResult->pNext;delete pTemp;return pResult;
}int main()
{TNode *pA = new TNode(1);TNode *pTail = AppendNode(pA, 3);pTail = AppendNode(pTail, 5);pTail = AppendNode(pTail, 6);pTail = AppendNode(pTail, 8);// 輸出：1->3->5->6->8PrintList(pA);TNode *pB = new TNode(2);pTail = AppendNode(pB, 3);pTail = AppendNode(pTail, 7);// 輸出：2->3->7PrintList(pB);TNode *pResult = MergeList(pA, pB);// 輸出：1->2->3->3->5->6->7->8PrintList(pResult);return 0;
}

總結

????????鏈表是一種常見的數據結構，它通過指針鏈接一系列的節點。通過這道題，我們學習了鏈表的數據結構，以及鏈表合并的操作。

????????另外，我們還為你留了一些課后的拓展作業，快來試一試吧！

????????1、給定一個單向鏈表，判斷鏈表中是否有環。

????????2、給定一個單向鏈表的頭節點，寫一個函數將其反轉。