如何用頭部/尾部實現克隆鏈表？

Question

我有下面的結構實現鏈表：

struct _node { 
    int item; 
    struct _node *next; 
} 

struct _list { 
    struct _node *head; 
    struct _node *tail; 
    int size; 
} 

我想編寫一個克隆鏈表的函數，而無需修改原始返回一個新的列表。我知道如何使用_node實現來做到這一點，但我不知道如何使用_list實現來做到這一點。

struct _node *cloneList (struct _node *head) { 
    if (head == NULL) return NULL; 

    struct _node *result = malloc(sizeof(struct _node)); 
    result->item = head->item; 
    result->next = cloneList(head->next); 
    return result; 
} 

這裏是我做了什麼：

struct _list *cloneList (struct _list *list) { 
    if (list == NULL) return NULL; 

    struct _list *result = malloc(sizeof(struct _list)); 
    result->size = list->size; 
    result->head = list->head; 
    result->tail = list->tail; 
    return result; 
} 

但這是一個有錯誤的實現，因爲它實際上並沒有克隆列表中，因爲指針頭尾仍然是相同的。

Answer 1

您必須將實際克隆列表元素的舊函數與僅克隆列表的「管理」部分的新函數結合使用。

爲此可以修改以前版本的有點：

struct _node *cloneList (struct _list *list, struct _node *head) { 
    if (head == NULL) return NULL; 

    struct _node *result = malloc(sizeof(struct _node)); 
    result->item = head->item; 
    if (head->next) 
    result->next = cloneList(list, head->next); 
    else 
    list->tail = result; 
    return result; 
} 

然後從一個新的函數內

struct _list *cloneFullList (struct _list *list) { 
    if (list == NULL) return NULL; 

    struct _list *result = malloc(sizeof(struct _list)); 
    result->size = list->size; 
    if (list->head != NULL) { 
     result->head = cloneList(result, list->head); 
     // tail will be set in cloneList as well. 
    } 
    else { 
     result->head = result->tail = NULL; 
    } 
    return result; 
}