如何將鏈表複製到另一個列表中？

Question

我正在研究數據結構和鏈表，但我沒有得到如何製作鏈表的副本的概念。有人可以解釋這一點，可能使用僞代碼或C代碼？

Answer 1

用於複製一個鏈表的邏輯是遞歸併且基於以下觀察：

1. 空列表的克隆是空列表。
2. 具有第一個節點x和其餘節點xs的列表的副本是x的副本，前綴爲xs的副本。

如果您在編碼C++的鏈表，這可能是非常乾淨：

struct Node { 
    int value; 
    Node* next; 
}; 

Node* Clone(Node* list) { 
    if (list == NULL) return NULL; 

    Node* result = new Node; 
    result->value = list->value; 
    result->next = Clone(list->next); 
    return result; 
} 

Answer 2

您知道如何將新節點添加到現有列表嗎？你知道如何遍歷（即迭代）列表嗎？複製列表只是同時執行這兩個操作（遍歷ListA;對於每個元素，複製元素並將其作爲新節點添加到ListB）。