如何在 Java 中使用复制构造函数正确复制链表？

Question

我无法正确使用复制构造函数来复制 LinkedList。

考虑这个例子：

public class LinkedList {
    
    public class Node {
        Node next;
        int val;
        Node(int val) {
            this.val = val;
            next = null;
        }
    }
    public Node head;
    public Node current;
    public LinkedList() {
        
    }
    
    
    public LinkedList(LinkedList another) {
        this.head = another.head;
        this.current = another.current;
    }
    
    public boolean empty() {
        return head == null;
    }
    
    public void insert(int e) {
    
        if (empty()) {
            head = current = new Node(e);
            return;
        }
        Node currNode = new Node(e);
        Node tmp = current;
        tmp.next = currNode;
        current = currNode;
        

    }
    
    public void display() {
        Node currNode = head;
        while (currNode != null) {
            System.out.println(currNode.val);
            currNode = currNode.next;
        }
    }
}

我使用复制构造函数复制了一个链表，main中的代码如下：

public class Main {
    public static void main(String [] args) {
        LinkedList ls = new LinkedList();
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        
        LinkedList another = new LinkedList(ls);
        
        another.display();
        another.insert(0);
        ls.display(); // expected output is 5 6 7 
    }
}

代码的输出是5 6 7 5 7 6 0，但我预计它是5 6 7，因为我复制了它，它不会影响ls。发生了什么？如何解决这个问题以获得预期的输出？

Answer 1

类似

public LinkedList(const LinkedList& another) {
    this->head = this->current = another.copy()
}

private LinkedList copy( const LinkedList& another ) {
    Node last_node = null;
    Node new_first = null;
    for ( Node next_node = another->head; next_node != null; 
          next_node = next_node->Next ) {
        Node new_node = new Node( next_node );
        if ( new_first == null )
            new_first = new_node;
        if ( last_node != null )
            last_node.Next = new_node
        last_node = next_node;
     }
     return new_first;
}

请注意，我还更改了复制构造函数的签名；一般来说，参数应该是 const 引用。另外，我的简单解决方案包含存储泄漏，因为它在从 another.

复制之前没有删除“this”的当前节点

Answer 2

您好，欢迎来到 Whosebug 社区

这是您的 post 的解决方案：

您可以修改LinkedList构造函数如下：

    public LinkedList(LinkedList another) {
        Node previous = another.head;
        Node temp = null;
        // represent a reference to the head of the new linkedList
        Node first = null;
    while (previous != null) {
        Node node = new Node(previous.val);
        if (first == null) {
            first = node;
            temp = first;
        } else {
            temp.next = node;
            temp = temp.next;
        }

        previous = previous.next;
    }

        // set the head
        this.head = first;
        // Temp hold a reference of the last node of the another passed as parameter
        this.current = temp;

}

我在main方法中添加了注释，显示插入前后的链表内容：

        public static void main(String [] args) {
        LinkedList ls = new LinkedList();
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        System.out.println("------------ begin display initial list ls");
        ls.display();
        System.out.println("------------ end display initial list ls");

        LinkedList another = new LinkedList(ls);

        System.out.println("------------ begin display another list before insert");
        another.display();
        System.out.println("------------ end display another list before insert");
        System.out.println("------------ Insert 0 in another linked list");

        another.insert(0);

        System.out.println("------------ begin display another list after insert");
        another.display();
        System.out.println("------------ end display another list after insert");
        System.out.println("--------Initial list must not be modified------------");
        ls.display(); // expected output is 5 6 7
        System.out.println("--------end------------");
    }

这是控制台中的结果

 ------------ begin display initial list ls
 5
 6
 7
 ------------ end display initial list ls
 ------------ begin display another list before insert
 5
 6
 7
 ------------ end display another list before insert
 ------------ Insert 0 in another linked list
 ------------ begin display another list after insert
 5
 6
 7
 0
 ------------ end display another list after insert
 --------Initial list must not be modified------------
 5
 6
 7
 --------end------------

我们得到了预期的结果。

如何在 Java 中使用复制构造函数正确复制链表？

How to properly copy a linked list using copy constructor in Java?

java

linked-list

copy-constructor