合并两个有序链表

-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

合并两个有序链表

回答

相关问题