2链表合并困难

Question

我正在尝试合并两个链表。我遇到的一个问题是，我如何让我的while循环即使在一个列表到达末尾后也能继续运行。

例如: List1取值: 1，3；列表2取值: 2,6,7,8；

理想的输出应该是: 1,2,3,6,7,8目前我的输出更像是1,2,3 (list1已经到达了末尾，所以循环停止，其他列表2的值不会添加到列表中)。

此外，我希望我的合并不会破坏我合并的原始2个列表，我如何才能做到这一点？

struct Node
{
    int value;
    Node *next;
};

void addNode(Node* &head, int x) 
{

    Node* temp = new Node;
    temp->value = x;
    temp->next = nullptr;

    if(!head) 
    { 
        head = temp;
        return;
    } 
    else 
    {
        Node* last = head;
        while(last->next) 
        last=last->next;
        last->next = temp;
    }
}


 void merge(Node * &head1, Node * &head2, Node * &head3)
 {
     while (head1 != nullptr && head2 != nullptr)
     {

        if (head1->value < head2->value)
        {
            addNode(head3, head1->value); 
            head1 = head1->next;
        }
        else
        {
            addNode(head3, head2->value);
            head2 = head2->next;
        }

     }
 }

主要功能：

int main()
{
    Node *head = nullptr;
    Node *head2 = nullptr;
    Node *head3 = nullptr;

    for (int i=0; i<=8; i+=2)
        addNode(head, i);

    for (int i=1; i<=5; i++)
        addNode(head2, i);

    merge(head, head2, head3);

    printList(head);
    printList(head2);
    printList(head3);

    system("PAUSE");
    return 0;
}

Answer 1

如果您忘记合并任何剩余的项目，请使用以下命令：

 // dont pass head1, head2 by reference in method call
 void merge(Node * head1, Node * head2, Node * &head3)
 {
     // and/or use other variables to avoid changing head1, head2
     Node * list1 = head1;
     Node * list2 =  head2;

     while (list1 != nullptr && list2 != nullptr)
     {

        if (list1->value < list2->value)
        {
            addNode(head3, list1->value); 
            list1 = list1->next;
        }
        else
        {
            addNode(head3, list2->value);
            list2 = list2->next;
        }

     }
     // merge any remaining list1 items
     while (list1 != nullptr)
    {
       addNode(head3, list1->value); 
       list1 = list1->next;
    }
     // merge any remaining list2 items
     while (list2 != nullptr)
    {
       addNode(head3, list2->value); 
       list2 = list2->next;
    }
 }

Answer 2

Nikos M.回答了你的第一个问题，他的回答很好，所以我不重复了。这个答案回答了你的第二个问题：

另外，我希望我的合并不会破坏我合并的原始2个列表，我如何才能做到这一点？

答案很简单:不要通过引用传递head1和head2：

void merge(Node * head1, Node * head2, Node * &head3)

事实上，我建议使用head1和head2 const指针：

void merge(const Node * head1, const Node * head2, Node * &head3)

Answer 3

一旦head1或head2变为null，while循环就会退出。我认为您需要添加一段额外的代码来追加非空列表中所有剩余的元素(我假设它们已经排序)。

 Node* lastElements = list1 != nullptr ? list1 : list2;
 while( lastElements != nullptr )
 {
     addNode(list3, lastElements->value);
     lastElements = lastElements->next;
 }

向Node添加一个构造函数，以便next始终初始化为nullptr。我最初读错了代码，我以为你错过了这个初始化，但是添加一个构造函数会简化你的代码，这意味着如果你在其他地方创建节点，你不会忘记初始化next指针。

Node( int initValue)
: value(initValue)
,  next(nullptr)
{}

并且你的addNode函数的开头变成了1行而不是3行。

Node* temp =  new Node(x);

如果合并不是破坏性的，就不要传入对head1和head2指针的引用。所以就像这样。

void merge( const Node* head1, const Node* head2, Node3*& outHead3)
{
     //copy pointers in order to iterate through list
     Node* current1 = head1;
     Node* current2 = head2;

     while( current1 != nullptr && current2 != nullptr)
     {
         //as before with relevant name changes
         .
         .
         .
     }

     Node* lastElements = current1 != nullptr ? current1 : current2;
     while( lastElements != nullptr )
     {
         addNode(outHead3, lastElements->value);
         lastElements = lastElements->next;
     }
}