交错2个链接列表C ++

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