2 .链表合并困难

Question

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

E。G: List1值:1,3;

理想的输出是: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

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 2

当head1或head2变为空时，while循环退出。我认为你想添加一个额外的代码片段，只是从非空列表追加所有剩余的元素(我假设他们已经排序)。

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

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

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

Answer 3

如果您忘记合并任何剩余的项，请使用:

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