如何用C++编写mergeSort的合并函数

Question

我正在学习C++，并试图编写合并函数，该函数将两个排序列表合并为一个排序列表。这应该在O(n(时间内运行。以下是我的代码：

LinkedList<T> LinkedList<T>::merge(const LinkedList<T>& other) const {
LinkedList<T> left = *this;
LinkedList<T> right = other;
LinkedList<T> merged;
if (left.size() <= 1) {
return left;
}
else{
while (left.size() > 0 && right.size() > 0){
if (left.front() <= right.front()){
merged.pushBack(left.front());
left.popFront();
}
else {
merged.pushBack(right.front());
right.popFront();
}
}
}
return merged;
}

这是我的测试：

Testing merge():
Left List: [(1)(3)(5)]  Right List: [(-1)(2)(10)(20)]
Merged: [(-1)(1)(2)(3)(5)]
Expected: [(-1)(1)(2)(3)(5)(10)(20)]

我认为发生这种情况是因为当其中一个列表变空时，循环就会停止。有人能建议我如何处理这个问题吗？非常感谢。

Answer 1

在main while循环之后，它有条件运行，直到两个数组都包含元素。因此，当其中一个为空时，它会退出，其中一个数组可能仍然包含剩余的元素。您还需要在外部添加while循环，以遍历添加到结果数组中的剩余元素。这是示例：

while (left.size() > 0)
{
merged.pushBack(left.front());
left.popFront();
}
while (right.size() > 0)
{
merged.pushBack(right.front());
right.popFront();
}