如何将一个链表复制到另一个链表中？

Question

我正在学习数据结构和链表，但是我不理解如何复制一个链表的概念。有人可以解释一下吗？最好使用伪代码或C代码。

- Vishwanath Dalvi

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

- templatetypedef

Answer 2

您知道如何将新节点添加到现有列表中吗？您知道如何遍历（即迭代）列表吗？复制列表只是同时执行这两个操作（遍历ListA；对于每个元素，复制该元素并将其作为新节点添加到ListB中）。

- Oliver Charlesworth

Answer 3

这篇帖子的答案已经被给出并接受 - 一切都很好！但是，如果有人正在寻找以 C# 为基础的迭代方法，那么这里有一个：

节点类：

public class Node
{
    public Node(int val)
    {
        Val = val;
    }

    public Node Next { get; set; }
    public int Val { get; }
}

这是迭代实现：

public Node CopyLinkedListIteratively(Node head)
{
    // validation:
    if (head == null) return null;

    // current node is always a 'new' node with value.
    Node currentNode = new Node(head.Val);

    // set copyList and previous to current node to start with - which is true at this point in time!
    Node copyList = currentNode;
    Node previous = currentNode;
    
    // move head one step forward as we already have copied its value.
    head = head.Next;

    // keep moving until we hit a null reference which is the end.
    while (head != null)
    {
        currentNode = new Node(head.Val); // create a new node every time as we move forward.
        previous.Next = currentNode; // set previous node's next to current node as previous node itself is one step behind the current.
        previous = previous.Next; // move prev pointer forward
        head = head.Next; // move head pointer forward as well
    }

    // return the reference to copyList.
    // copyList and previous both started off pointing to the currentNode, then in the while loop
    // previous kept moving forward till all nodes are copied.
    // copyList reference never moved from its position so its still pointing at the start.
    return copyList;
}

时间复杂度：O(n) 空间复杂度：O(n) 其中n表示链表中节点的数量。

使用递归或迭代方法是个人偏好，但我建议在使用递归时考虑函数调用栈。 单元测试：

[Test]
public void CopyLinkedListIterativelyTest()
{
    Node head = new Node(1);
    head.Next = new Node(2);
    head.Next.Next = new Node(3);
    head.Next.Next.Next = new Node(4);
    head.Next.Next.Next.Next = new Node(5);

    var actual = runner.CopyLinkedListIteratively(head);

    while (actual != null)
    {
        Assert.AreEqual(head.Val, actual.Val);
        actual = actual.Next;
        head = head.Next;
    }
}

- Yawar Murtaza

Answer 4

递归克隆解决方案的Java版本。

伪代码：

1. 每个节点都是一个新初始化的节点
2. 递归调用克隆函数为每个节点创建一个新节点

程序[JAVA]：

public class Program
{
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5,null);
        ListNode node4 = new ListNode(4,node5);
        ListNode node3 = new ListNode(3,node4);
        ListNode node2 = new ListNode(2,node3);
        ListNode node1 = new ListNode(1,node2);
        ListNode head = node1;
        //Printing to display the address
        System.out.println(head +"->" + head.next + "->" + head.next.next + "->" + head.next.next.next + "->" + head.next.next.next.next + "->" + head.next.next.next.next.next);
        ListNode newClone = Clone(head);
        while(newClone.next != null){
            System.out.print(newClone.getAddress() + "->");
            newClone = newClone.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode getAddress() {return this; }
    }

    public static ListNode Clone(ListNode nextNode) {
        if (nextNode == null) return nextNode;    
        ListNode newNode = new ListNode();
        newNode.val = nextNode.val;
        newNode.next = Clone(nextNode.next);
        return newNode;
    }
}

- Rahul Kannan G