合併兩個有序鏈表

-1

我在這個問題一個疑問：link我下面這個方案：合併兩個有序鏈表

if((headA==NULL)&&(headB==NULL) 
    return NULL; 
if((headA!=NULL)&&(headB==NULL)) 
    return headA; 
if((headA == NULL)&&(headB!=NULL)) 
    return headB; 
if(headA->data < headB->data) 
    headA->next = MergeLists(headA->next, headB); 
else if(headA->data > headB->data) 
{ 
    Node* temp = headB; 
    headB = headB->next; 
    temp->next = headA; 
    headA = temp; 
    headA->next = MergeLists(headA->next, headB); 
} 
return headA;

我得到的是，當headA->data < headB->data那麼我們只需將headA指針移動到下一個節點。但是當headA->data > headB->data時，我們創建一個臨時指針，將它指向headA指向的位置，並將headB移動到下一個節點。我不明白的是：

如何將預先排序獲取鏈接到這個新的臨時節點的節點，我已經創造出來的？你能指出我的代碼
此外，headA指針指向第二個條件後？它指向新節點嗎？

來源

2017-05-23 Monte

如果你通過與你的調試器單步執行代碼，它會顯示：

if(headA == NULL) return headB; if(headB == NULL) return headA;

這也可以不用遞歸方法來實現你到底發生了什麼事情，而且他們看到事情發生時的價值。 – NathanOliver

如果列表具有共同的數據值，則這不起作用。嘗試將列表與同一列表的副本合併。 – pat

您在代碼中至少缺少一個''''''。 – crashmstr

的代碼有效名單B移動頭元件到列表A.

Node* temp = headB; 
headB = headB->next;

temp在列表乙頭指向，並headB在列表乙尾指向。實際上，列表B頭已經從列表中彈出。

temp->next = headA;

列表A現在附加到彈出的頭部。

headA = temp;

並列出現在設置列表從列表B中的原頭，再加上原有名單A.

合併然後繼續完全一樣，如果列表A具有較小的頭，它現在這樣做是因爲列表B中的下一個元素不能小於它。

此代碼無法處理兩個列表具有相同頭數據值的情況。在這種情況下，它只是返回列表A而不合並尾部。

不知道爲什麼你不能只是做最後兩種情況：

if(headA->data < headB->data) { 
    headA->next = MergeLists(headA->next, headB); 
    return headA; 
} 
else { 
    headB->next = MergeLists(headA, headB->next); 
    return headB; 
}

，並保持它的簡單和對稱。

您也可以在前三種情況下簡化爲以下兩種：

Node *merge_lists(Node *headA, Node *headB) 
{ 
    Node *head; 
    Node **nextPtr = &head; 

    while (headA && headB) { 
     Node **headMin = (headA->data < headB->data) ? &headA : &headB; 
     *nextPtr = *headMin; 
     nextPtr = &(*headMin)->next; 
     *headMin = *nextPtr; 
    } 

    *nextPtr = headA ? headA : headB; 
    return head; 
}

來源

2017-05-23 15:53:00 pat

合併兩個有序鏈表

回答

相關問題