交错2个链表C++

Question

我这里有解决方案的代码：

// Pre-condition: The fronts of two linked lists are provided.
// Post-condition: A linked list is returned that is the result of
// interleaving the elements from each provided list. 
// (e.g. {1, 2, 3} & { 4, 5, 6} would return {1, 4, 2, 5, 3, 6}

Node* interleave( Node*& front1, Node*& front2 ) {
    if( !front1 ) return front2;
    if( !front2 ) return front1;

    Node* third = front1->next; //this will become the third element
    Node* fourth = front2->next; // this will be come the fourth element

    front1->next = front2;
    front2->next = third;

    third = interleave(third, fourth);

    return front1;  
}

我有点理解它，但我永远不能想出这样的东西，因为我非常不擅长递归。有没有其他非递归的方法来解决这个问题呢？如果是这样，你能给我一个提示吗？我试过这个：

Node* interleave( Node*& front1, Node*& front2 ) {
    Node* newNode = new Node;
    while(front1!=NULL && front2!=NULL){
        newNode = front1->next;
        newNode = front2->next;
        front1 = front1->next;
        front2 = front2->next;
     }
    return newNode;
}

我肯定这是错的，但这是我现在唯一能想到的。请帮帮忙。谢谢

Answer 1

您的代码中有几个错误：

Node* interleave( Node*& front1, Node*& front2 )

我认为没有必要引用指针，因为front1中的第一项将一直是第一项，并且您根本不需要与front2打交道。

Node* newNode = new Node;
while(front1!=NULL && front2!=NULL){
    newNode = front1->next;

这会导致内存泄漏-您至少分配了sizeof(Node)字节，但随后您丢失了对指针的引用，并且您将无法再删除它。另外，您没有对newNode做任何事情，所以您也可以把它扔掉。

front1 = front1->next;
front2 = front2->next;

基本上，您告诉我们front1更倾向于指向下一个元素，而且由于您传递了对front1的引用，所以您正在更改真正的指针。最终，front1或front2将为空，循环将终止，因此两个给定参数中至少有一个将变得无用。下一步你永远不会改变，所以顺序将保持不变--你只需浏览列表即可。

一种方法是将Front2的值设置为front1->next，然后交换指针并再次迭代：

Node *a = front1, *b = front2;
while (a && b) {
    Node* tmp = a->next;
    a->next = b;
    b = tmp;
    a = a->next;
}
return front1;

我没有对此进行测试，但它应该接近正常工作。如果您使用的是stl，那么可以用std:: swap ()替换详细的交换代码。想法很简单:假设你有两个列表：

A -> B -> C -> NULL

D -> E -> F -> NULL

你说A的下一项将是第二个列表中的第一个元素，所以D：

A -> D -> E -> F -> NULL

然后第二个列表变成了古老的A的后继者，所以B -> C ->为空。然后将a前进以指向其新的next，即D，因此您现在拥有：

D -> E -> F -> NULL

B -> C -> NULL

然后你重复一遍：

D -> B -> C -> NULL

E -> F -> NULL

B -> C -> NULL

F -> NULL

依此类推，直到满足NULL。然后，仍然指向A的front1应该具有正确的序列(即，除非我大错特错:p )

Answer 2

尝试在一张纸上并行绘制两个链表。在节点中放一些数字，只是为了区分它们。考虑如何将它们重新连接起来，形成一个单独的列表，从头部(或“前面”)开始，向下递增。请注意，您必须跟踪一些特殊节点，如结果列表的第一个节点和其他几个节点。这种模式应该会变得清晰。

(请注意，不需要使用new构造新节点。)