Дублирующий элемент из связанного списка в новом списке

Question

Im пытается скопировать в глубину список узлов. , например мой список, как показано ниже:

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