c++ - 递归复制链表

Question

在谷歌搜索了一段时间后，我得出的结论是我被难住了。

问题:

递归地复制链表(以及反向复制，但我稍后会过那个桥。)

我有以下代码:

// In list.h
struct node {
    int data;
    node * next;
}

// In list.cpp
// Recursive copy wrapper
int list::copy() {                              
    if(!head) {                                 
        return 0;                               
    }                                           
    node *new_node = NULL;
    return copy(new_node, head);                                          
}                                               

// Recursive copy function
int list::copy(node *& dest, node * src) {      
    if(!src) {                                  
        dest = NULL;                            
        return 0;                               
    }                                           

    dest = new node();                          
    dest->data = src->data;
    // *dest->next = src->next;* // Not sure what to do here?

    return copy(dest->next, src->next) + 1; // count number of nodes copied  
}

注意:这不是家庭作业，而是准备技术面试考试的问题。

在这一点上，我相当确定我无法靠自己实现这一目标，因此我们将不胜感激。提前致谢!

Answer 1

根据我的理解，首先需要递归复制列表，新头部的引用需要指向拷贝的头部；这可以按如下方式完成。

int list::copy(node *& dest, node * src)
{      
    if(!src)
    {                                  
        dest = NULL;                            
        return 0;                               
    }                                           

    dest = new node();                          
    dest->data = src->data;

    node* TailCopy = null; // reference to copy of remaining list

    int TotalNumOfNodes = 1 + copy(Tail, src->next) + 1;

    dest->next = TailCopy; // let copy of head refer to copy of tail

    return TotalNumOfNodes;
}