合并链表

Question

我正在尝试在c++中合并两个链表，但没有就位。但每次创建的新列表在到达一个或另一个列表的nullptr后都会发出以下数字。

MyLinkedList mergeTwoLinkedList(MyLinkedList b) {
        MyLinkedList c;

        node *tempa = this->head;
        node *tempb = b.head;

        if (b.head == nullptr)
            return *this;

        if (this->head == nullptr)
            return b;

        if (tempa && tempb) {
            do
            {
                if ((tempa->val) <= (tempb->val)) {
                    c.addAtTail(tempa->val);
                    tempa = tempa->next;

                } else if ((tempa->val) >= (tempb->val)) {
                    c.addAtTail(tempb->val);
                    tempb = tempb->next;
                }
            }
            while (tempa && tempb);
            return c;
        }
}

Answer 1

这是一种非常常见的合并排序模式。首先让我通过删除冗余测试来简化您的循环(因为如果值A不小于B，则根据定义它大于)。

while (tempa && tempb)
{
    if (tempa->val <= tempb->val) {
        c.addAtTail(tempa->val);
        tempa = tempa->next;
    } else {
        c.addAtTail(tempb->val);
        tempb = tempb->next;
    }
}

所以，接下来会发生的事情是，一旦任何一个列表到达末尾，你的循环就会结束，并且不会再添加任何值。

在我看来，对于这个问题，绝对最简单和最具可读性的解决方案是在之后再添加两个循环，这两个循环只附加剩余的尾巴：

for(; tempa; tempa = tempa->next)
{
    c.addAtTail(tempa->val);
}

for(; tempb; tempb = tempb->next)
{
    c.addAtTail(tempb->val);
}

常见的其他解决方案是，主循环直到两个指针都为空才终止，但这需要在循环内进行更多的测试，这可能会降低性能，并且肯定会降低可读性。

现在，如果您确实使用它进行合并排序，您甚至不需要单独的列表。您可以通过修补列表节点将一个列表合并到另一个列表中。这使得添加整个尾部成为一种O(1)操作，这意味着在合并期间不会发生分配。如果合适的话，我将把它作为练习留给您。

Answer 2

假设正确定义了addToTail()。您显示的代码中有一个缺陷。在循环中：

do
{
    if ((tempa->val) <= (tempb->val)) {
        c.addAtTail(tempa->val);
        tempa = tempa->next;

    } else if ((tempa->val) >= (tempb->val)) {
        c.addAtTail(tempb->val);
        tempb = tempb->next;
    }
} while (tempa && tempb);

while条件正在检查tempa && tempb -->您正在检查它们是否都有效。可能存在一个列表比另一个列表具有更多节点的情况。在这种情况下，您会错过从其他列表中复制节点的机会。要更正此缺陷，您可以按如下方式更改代码：

MyLinkedList mergeTwoLinkedList(MyLinkedList b) {
    MyLinkedList c;

    node *tempa = this->head;
    node *tempb = b.head;

    if (b.head == nullptr)
        return *this;

    if (this->head == nullptr)
        return b;

    if (tempa && tempb) {
        do
        {
            if ((tempa->val) <= (tempb->val)) {
                c.addAtTail(tempa->val);
                tempa = tempa->next;

            } else if ((tempa->val) >= (tempb->val)) {
                c.addAtTail(tempb->val);
                tempb = tempb->next;
            }
        }
        while (tempa && tempb); /* here  one of the tempa or tempb list may still have some nodes to copy to 'c' list */

        if (tempa) { // checking whether tempa list has more nodes to cover
            while (tempa) {
                c.addAtTail(tempa->val);
                tempa = tempa->next;
            }
        } else if (tempb) { // checking whether tempb list has more nodes to cover
            while (tempb) {
                c.addAtTail(tempb->val);
                tempa = tempb->next;
            }
        }
    }
    return c;       // returning the new list after merging
}

这应该可以解决您的问题。希望这能有所帮助，谢谢:)