c++ - 合并链表

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

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

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