为什么在排序链表上的这种合并实现总是将两个列表都设置为 NULL，而只有一个应该设置一个列表?

Question

老实说，我已经在这里呆了大约 10 个小时，尝试了一个又一种方法来让它工作。我正在尝试创建一个第三个列表，该列表是 2 个列表合并在一起并从低到高排序(没有重复(，然后将第一个列表设置为新列表，从而将第二个列表合并到第一个列表中。但是每当我运行程序时，我都会得到 listData == NULL，即使在 newListCurr 绝对应该向 newList 添加元素的测试用例中也是如此。我一直很难使用链表，所以也许我误解了一些基础知识，但我一生都无法弄清楚这一点。该方法不需要声明单个新节点，并且只能具有 O(n( 的时间复杂度，这使得这变得更加困难。我已经尝试了几种方法，例如尝试将它们直接插入 listData(第一个列表(，但有一个一致的问题，即 curr 指针实际上不会影响它们各自的 listData。

编辑：假定列表在合并之前排序。

这是合并方法，其他一切都按预期工作，只是合并方法搞砸了。

template <class ItemType>
void SortedList<ItemType>::merge(SortedList& list) {
Node<ItemType> * curr1 = listData;
Node<ItemType> * curr2 = list.listData;
Node<ItemType> * newList = NULL;
Node<ItemType> * newListCurr = newList;
while(curr2 != NULL || curr1 != NULL) {
if(curr2 == NULL) {
newListCurr = curr1;
curr1 = curr1->next;
newListCurr = newListCurr->next;
}
else if(curr1 == NULL) {
newListCurr = curr2;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
else if(curr1->info < curr2->info) {
newListCurr = curr1;
curr1 = curr1->next;
newListCurr = newListCurr->next;
} else if (curr2->info < curr1->info) {
newListCurr = curr2;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
else if (curr1->info == curr2->info) {
newListCurr = curr1;
curr1 = curr1->next;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
}
list.listData = NULL;
listData = newList;
}

编辑：我为那些可能有同样问题的人找到了解决方案。我需要将 newList 和 newListCurr 设置为一个节点，然后才能使用 newListCurr 修改 newList 的其余部分。这是我更新的代码：

template <class ItemType>
void SortedList<ItemType>::merge(SortedList& list) {
Node<ItemType> * curr1 = listData;
Node<ItemType> * curr2 = list.listData;
Node<ItemType> * newList = NULL;
Node<ItemType> * newListCurr = newList;
if(curr2 != NULL || curr1!= NULL) {
if(curr2 == NULL) {
newListCurr = curr1;
curr1 = curr1->next;
} else if(curr1 == NULL) {
newListCurr = curr2;
curr2 = curr2->next;
} else if(curr1->info < curr2->info) {
newListCurr = curr1;
curr1 = curr1->next;
} else if (curr2->info < curr1->info) {
newListCurr = curr2;
curr2 = curr2->next;
} else if (curr1->info == curr2->info) {
newListCurr = curr1;
curr1 = curr1->next;
curr2 = curr2->next;
}
newList = newListCurr;
}
while(curr2 != NULL || curr1 != NULL) {
if(curr2 == NULL) {
newListCurr->next = curr1;
curr1 = curr1->next;
newListCurr = newListCurr->next;
}
else if(curr1 == NULL) {
newListCurr->next = curr2;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
else if(curr1->info < curr2->info) {
newListCurr->next = curr1;
curr1 = curr1->next;
newListCurr = newListCurr->next;
} else if (curr2->info < curr1->info) {
newListCurr->next = curr2;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
else if (curr1->info == curr2->info) {
newListCurr->next = curr1;
curr1 = curr1->next;
curr2 = curr2->next;
newListCurr = newListCurr->next;
}
}
list.listData = NULL;
listData = newList;
}

Answer 1

newList

在顶部设置为 NULL，并且永远不会重新分配。 当您在末尾设置self. listData = newList;时，newList 仍为 NULL。

也许你认为如果你把newListCurr设置为某件事，它就会设置newList——它不会。它们是独立的指针。

Answer 2

在原始函数代码中有两个问题。第一个是指针newList在函数内未更改且始终等于 NULL。

Node<ItemType> * newList = NULL;

此空指针分配给数据成员listData

listData = newList;

第二个问题是你总是在更改指针newListCurr而不是指针newListCurr->next的当前值，例如在这个if语句中

if(curr2 == NULL) {
newListCurr = curr1;
^^^^^^^^^^^^^^^^^^^^ 
curr1 = curr1->next;
newListCurr = newListCurr->next;
}

在新更新的函数实现中，您可以避免此错误，因为现在您确实在更改当前指针的数据成员nextnewListCurr

if(curr2 == NULL) {
newListCurr->next = curr1;
^^^^^^^^^^^^^^^^^^^^^^^^^
curr1 = curr1->next;
newListCurr = newListCurr->next;

然而，该函数的新实现过于复杂，因为相同的代码实际上在第一个 if 语句中重复。

如果使用指向指针的指针，则可以更轻松地实现该函数。我不知道你的类是如何定义的，所以我定义了我的一个简单的类。

该函数可以插入重复项，但您可以使用未插入重复项的附加 if 语句以这种方式更改它。

这是一个演示程序。

#include <iostream>
template <class ItemType>
class SortedList
{
private:
struct Node
{
ItemType info;
Node *next;
} *listData = nullptr;
public:
void insert( const ItemType &info )
{
Node **tail = &listData;
while ( *tail ) tail = &( *tail )->next;
*tail = new Node { info, nullptr };
}
void merge( SortedList<ItemType> & list )
{
Node *newListData = nullptr;
Node **current = &newListData;
Node **first   = &listData;
Node **second  = &list.listData;
while ( *first && *second )
{
if ( ( *second )->info < ( *first )->info )
{
*current = *second;
*second = ( *second )->next;
current =  &( *current )->next;
}
else
{
*current = *first;
*first = ( *first )->next;
current =  &( *current )->next;
}
}
while ( *first )
{
*current = *first;
*first = ( *first )->next;
current =  &( *current )->next;
}
while ( *second )
{
*current = *second;
*second = ( *second )->next;
current =  &( *current )->next;
}
listData = newListData;
}
friend std::ostream & operator <<( std::ostream &os, const SortedList<ItemType> &list )
{
for ( const SortedList<ItemType>::Node *current = list.listData; current; current = current->next )
{
os << current->info << " -> ";
}
return os << "null";
}
};
int main() 
{
SortedList<int> list1;
SortedList<int> list2;
const int N = 10;
for ( int i = 0; i < N; i++ )
{
if ( i % 2 == 0 ) list1.insert( i );
else list2.insert( i );
}
std::cout << list1 << 'n';
std::cout << list2 << 'n';
list1.merge( list2 );
std::cout << list1 << 'n';
std::cout << list2 << 'n';
return 0;
}

程序输出为

0 -> 2 -> 4 -> 6 -> 8 -> null
1 -> 3 -> 5 -> 7 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
null