java - 新列表中链表的重复项

Question

我正在尝试深入复制节点列表。 例如我的列表如下:

Node n = new Node(1,new Node(12, new Node(34, new Node(3, Node.NIL))));

我的功能是:

    public Node copy() {

       Node initial= this;
       Node duplicate=new Node(initial.getItem());

       while(Node.NIL!=initial.getNext()){

           initial=initial.getNext();
           Object a = initial.getItem();
           duplicate.next=new Node(a);
       }

       return duplicate;
    } 

所以当我这样做时，输出列表是重复的 [1,3]。我不明白 12 和 34 在哪里。

Answer 1

在这一步 duplicate.next=new Node(a); 中，您每次都会覆盖 duplicate.next 的先前值。创建下一个节点时，您应该在每一步更改对 duplicate 的引用。

您可以使用递归来创建下一个节点的副本并在之后创建新节点:

    public Node copy() {
        Node initial= this;
        Node copyNext = this.getNext() == NIL? NIL : this.getNext().copy();
        Node duplicate = new Node(initial.getItem());
        duplicate.next = copyNext;
        return duplicate;
    }

并且没有递归:

    public Node copy() {

        Node currentNode= this;
        Node firstDuplicate = new Node(currentNode.getItem()); //save reference for first node to return
        Node currentDuplicate=firstDuplicate;

        while(Node.NIL!=currentNode.getNext()){
            Node nextNode = currentNode.getNext();
            Node nextCopy = new Node(nextNode.getItem()); //create copy of next
            currentDuplicate.next = nextCopy; //assign this copy as next for current duplicated node
            currentDuplicate = nextCopy; //change reference for current duplicated node to copy 
            currentNode = nextNode; 
        }

        return firstDuplicate;
    }

如果我没理解错的话，您需要创建还原列表。在这种情况下，您不需要创建初始列表的新副本。

    public Node reverse() {
        Node head = NIL; //initial we have a empty list

        Node current = this; //set cursor to current node

        while (current != NIL) {
            Node copy = new Node(current.getItem()); //create a copy of current node
            copy.next = head; //set head node as next for copy 
            head = copy; //now move head to copy 
            current = current.next; // move cursor for next position
        }

        return head;
    }

要使用递归创建反向列表，您只需要额外的方法来保留对先前创建的副本的引用:

    public Node reverse() {
        if (this == NIL) {
            return NIL;
        }

        return reverse(new Node(this.getItem(), NIL), this.getNext());
    }

    private Node reverse(Node head, Node tail) {
        Node copy = new Node(tail.getItem()); 
        copy.next = head;
        if (tail.getNext() == NIL) {
            return copy;
        }
        return reverse(copy, tail.next);
    }