c++ - 合并两个排序的链表

我对此问题有疑问：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指针指向何处？它指向新节点吗？

最佳答案

该代码有效地将head元素从列表B移动到列表A。

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

temp指向列表B的开头，headB指向列表B的结尾。实际上，列表B头已从列表中弹出。

temp->next = headA;

现在将列表A附加到弹出的头部。

headA = temp;

现在，列表A设置为列表，列表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;
}

并保持简单和对称。

您还可以将前三种情况简化为以下两种情况：

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

这也可以不用递归来完成：

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;
}