從新列表中的鏈接列表中複製項目

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

Answer 2

public Node reverse(){ 

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

    while(Node.NIL!=p.getNext()){ 
     Node nextNode = p.getNext(); 
     Node nextCopy = new Node(nextNode.getItem()); 
     currentDuplicate.n = nextCopy; 
     currentDuplicate = nextCopy; 
     p = nextNode; 
    } 


      /* If the list is empty */ 
      if(firstDuplicate == NIL) 
       return Node.NIL; 

      /* If the list has only one node */ 
      if(firstDuplicate.n == Node.NIL) 
       return firstDuplicate; 

     // Node reverseRest = new Node(p.getItem(),Node.NIL); 
      Node rest = new Node(); 
      rest = firstDuplicate.getNext(); 

      firstDuplicate.setNext(Node.NIL); 
     // Node reverseRest=new Node(p.getItem(),reverseRest); 

     Node reverseRest=new Node(); 
      reverseRest = rest.reverse(); 

      /* Join the two lists */ 
      rest.setNext(firstDuplicate); 
      //p=this; 
     // p=p.nthNext(0); 
      return reverseRest; 
     }