c++ - 交错 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

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

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