C++解決合并兩個排序的鏈表問題

第C++解決合并兩個排序的鏈表問題目錄題目描述：示例：解題思路：測試代碼：

題目描述：

輸入兩個遞增的鏈表，單個鏈表的長度為n，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。

數(shù)據(jù)范圍：n為0~1000，節(jié)點值為-1000~1000

要求：空間復雜度O(1)，時間復雜度O(n)

如輸入{1,3,5},{2,4,6}時，合并后的鏈表為{1,2,3,4,5,6}，所以對應的輸出為{1,2,3,4,5,6}，轉換過程如下圖所示：

或輸入{-1,2,4},{1,3,4}時，合并后的鏈表為{-1,1,2,3,4,4}，所以對應的輸出為{-1,1,2,3,4,4}，轉換過程如下圖所示：

示例：

輸入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

解題思路：

本題考察數(shù)據(jù)結構鏈表的使用。有兩種解法：

遍歷比較。建立一個新的頭節(jié)點head后，用cur指針指向下一節(jié)點；然后依次比較兩個子鏈表節(jié)點的值大小，誰小先塞誰，塞完就將其指向下一個節(jié)點；直到某個子鏈表遍歷完，將cur的next指向沒遍歷完的那個鏈表當前的節(jié)點。

遞歸。從pHead1和pHead2的頭節(jié)點開始比較，誰小就返回誰，然后其下一個指向，指向Merge函數(shù)的結果，Merge輸入的兩個鏈表為小的一方的next和大的一方的頭節(jié)點，也就是用下一個值和它繼續(xù)比誰更??；依次類推，遞歸中斷的標志是有其中一個子鏈表指向nullptr，返回另一方即可。

測試代碼：

解法一，遍歷：

structListNode{

intval;

structListNode*next;

ListNode(intx):

val(x),next(NULL){

classSolution{

public:

ListNode*Merge(ListNode*pHead1,ListNode*pHead2){

ListNode*head=newListNode(-1);

ListNode*cur=head;

while(pHead1pHead2)

if(pHead1-val=pHead2-val)

cur-next=pHead1;

pHead1=pHead1-next;

else{

cur-next=pHead2;

pHead2=pHead2-next;

cur=cur-next;

cur-next=pHead1pHead1:pHead2;

returnhead-next;

};

解法二，遞歸：

structListNode{

intval;

structListNode*next;

ListNode(intx):

val(x),next(NULL){

classSolution{

public:

ListNode*Merge(ListNode*pHead1,ListNode*pHead2){

if(!pHead1)

returnpHead2;

if(!pHead2)

returnpHead1;

if(pHead1-val=pHead2-val)

pHead1-next=Merge(pHead1-next,pHead2);

returnpHe