合併兩個排序的鏈接列表

Question

我想合併兩個排序的鏈接列表。這裏我只是想實現我自己的算法。當然，互聯網上有很多解決方案。代碼是：

Node* MergeLists(Node *headA, Node* headB) 
{ 
    int countA = 0, countB = 0; 
    while(headA){countA++; headA = headA->next;} 
    while(headB){countB++; headB = headB->next;} 
    Node *res, *tres; 
    res = new Node(); 
    res->next = NULL; 
    tres = res; 
    for(int i = 0; i < countA+countB-1; i++) 
    { 
     Node* temp = new Node(); 
     temp->next = NULL; 
     tres->next = temp; 
     tres = tres->next; 
    } 
    while(headA != NULL && headB != NULL) 
    { 
     if(headA->data > headB->data) 
     { 
      res->data = headB->data; 
      res = res->next; 
      headB = headB->next; 
     } 
     else if(headA->data < headB->data) 
     { 
      res->data = headA->data; 
      res = res->next; 
      headA = headA->next; 
     } 
    } 
    while(headA) 
    { 
     res = headA; 
    } 
    while(headB) 
    { 
     res = headB; 
    } 
    return res; 
} 

這只是一個函數，它返回合併鏈表的首地址。

考慮此輸入/輸出例如：

Input (stdin): 

3 
4 
1 3 5 6 
3 
2 4 7 
1 
15 
1 
12 
0 
2 
1 2 

My Output (stdout) 

0 0 0 0 0 0 0 
0 0 
0 0 

Expected Output 
1 2 3 4 5 6 7 
12 15 
1 2 

所以，我的輸出打印所有零。這是由於在這段代碼中的問題：

Node *res, *tres; 
    res = new Node(); 
    res->next = NULL; 
    tres = res; 
    for(int i = 0; i < countA+countB-1; i++)// this is creating a new linked list. 
    { 
     Node* temp = new Node(); 
     temp->next = NULL; 
     tres->next = temp; 
     tres = tres->next; 
    } 

我認爲tres和res之間的聯繫不正常發生。你能告訴我如何改正這個問題嗎？

更新：

Node* MergeLists(Node *headA, Node* headB) 
{ 

    int countA = 0, countB = 0; 
    Node* tempA, *tempB; 
    tempA = headA; tempB = headB; 
    while(headA){countA++; tempA = tempA->next;} 
    while(headB){countB++; tempB = tempB->next;} 
    Node *res, *tres; 
    res = new Node(); 
    res->next = NULL; 
    tres = res; 
    for(int i = 0; i < countA+countB-1; i++) 
    { 
     Node* temp = new Node(); 
     temp->next = NULL; 
     tres->next = temp; 
     tres = tres->next; 
    } 
    while(headA != NULL && headB != NULL) 
    { 
     if(headA->data > headB->data) 
     { 
      res->data = headB->data; 
      res = res->next; 
      headB = headB->next; 
     } 
     else if(headA->data < headB->data) 
     { 
      res->data = headA->data; 
      res = res->next; 
      headA = headA->next; 
     } 
    } 
    if(headA) 
    { 
     res= headA; 
     //res = res->next; 
     //headA = headA->next; 
    } 
    if(headB) 
    { 
     res = headB; 
     //res = res->next; 
     //headB = headB->next; 
    } 
    return res; 
} 

這次~ no response on stdout ~

Answer 1

問題在於這部分代碼。

while(headA){countA++; headA = headA->next;} 
while(headB){countB++; headB = headB->next;} 

執行該循環之後，兩個headA & headB都指向NULL; 所以當

while(headA != NULL && headB != NULL) 

循環啓動，它甚至不進入循環。由於此循環負責分配值並且不會進入此循環。因此，所有的值都設置爲默認值0.

由於@Slava提到你甚至不需要這個循環。當你直接迭代節點並且可以在發生NULL時停止。

創建一個臨時指針並使用該指針來計算countA和countB。

喜歡的東西

Node* temp; 
temp = headA; 
while(temp){countA++; temp = temp->next;} 
temp = headB; 
while(temp){countB++; temp = temp->next;} 

而且，這可能會導致無限循環。請增加循環內的節點。或者只是將條件改爲if而不是while。

while(headA) 
    { 
     res = headA; 
    } 
    while(headB) 
    { 
     res = headB; 
    } 

更新 -

另一個問題： 這個計算，這是指向最後一個元素後，您返回水庫。因此輸出將只是一個數字。

你可以做的是

tres = res; 
for(int i = 0; i < countA+countB-1; i++) 
{ 
    ... 
} 
tres = res; // Add this line, so your keeping track of the original head 
while(headA != NULL && headB != NULL) 

最後return tres;回資源代替;有了這個，你會回到原來的頭。

Answer 2

節點應該包含這樣的 - 你正在創建一個新的節點，並將其分配給鏈的末端，但它沒有保存價值可言，所以這個值可能只是默認爲零。

Answer 3

 res = res->next; <--- 

while(headA) 
{ 
    res = headA; 
} 
while(headB) 
{ 
    res = headB; 
} 
return res; 

你返回res指向結束而不是頭部的指針。 另外while（headB/headA）假設在列表的末尾添加提醒，但實際上會循環無限，因爲沒有指針的增量。

Answer 4

你並不需要計算元素，預先創建結果列表，並使用這麼多的循環，在一個循環中做的一切：

Node* MergeLists(Node *headA, Node* headB) 
{ 
    Node *res = nullptr; 
    Node **ptr = &res; 
    while(headA || headB ) { 
     Node *curr = new Node; 
     curr->next = nullptr; 
     *ptr = curr; 
     ptr = &curr->next; 
     if(headB == nullptr || (headA && headA->data < headB->data)) { 
      curr->data = headA->data; 
      headA = headA->next; 
     } else { 
      curr->data = headB->data; 
      headB = headB->next; 
     } 
    } 
    return res; 
} 

注意：你不應該從一個函數返回原始指針 - 它很容易導致到內存泄漏。您應該使用智能指針。