對于鏈表，《劍指offer》中感覺有些地方不妥，前面講過鏈表的頭指針是指向一個指針的指針，即指向頭結點的指針的指針。但是后面在鏈表的使用中輸入的頭指針只是指向鏈表的頭結點的指針。

后面看《c和指針》時看到單鏈表這一塊，鏈表的表示時用一個根指針來表示鏈表的起始位置，根指針指向鏈表的第一個節點，根指針只是一個指針，不包含任何數據。當我們需要改動鏈表，如果可能改動根指針，如將根指針改為指向另一個節點，則傳參時需要以指針形式傳遞才可以改動根指針的值，即參數就變為了指向根指針的指針，也是指向第一個節點的指針的指針。而當我們不會改動鏈表根指針時輸入參數不需要輸入指針，直接輸入根指針就可以了。

題目：合并兩個排序的數組

遞歸的方法：（附上《劍指offer》中的解法）

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* pMergedHead = NULL;if(pHead1->m_nValue < pHead2->m_nValue){pMergedHead = pHead1;pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);}else{pMergedHead = pHead2;pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);}return pMergedHead; }

循環的方法：（在這里我寫了一個循環的方法，這里還是輸入參數為指向頭結點的指針，因為原列表的頭指針可以不變，但此時實際上鏈表1和鏈表2已經不是原來的鏈表了；個人感覺應該將兩個根指針置為NULL比較好）

ListNode* MergeSorted2Lists(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == NULL)return pHead2;else if(pHead2 == NULL)return pHead1;ListNode* pListNewSmall = pHead1;ListNode* pListNewLarge = pHead2;if(pListNewSmall->m_nValue > pListNewLarge->m_nValue){swap(pListNewLarge,pListNewSmall);}ListNode* pMergedHead = pListNewSmall;while(pListNewLarge){while( pListNewSmall->m_pNext && pListNewSmall->m_pNext->m_nValue <= pListNewLarge->m_nValue ){pListNewSmall = pListNewSmall->m_pNext;}ListNode* tempNode = pListNewSmall->m_pNext;pListNewSmall->m_pNext = pListNewLarge;pListNewSmall = pListNewLarge;pListNewLarge = tempNode;}return pMergedHead; }



總結

以上是生活随笔為你收集整理的面试题整理 4 合并两个排序的数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。