Duplicate item from linked list in new list

Question

Im trying to copy in deep a list of node . for example my list is as below:

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

and my function as :

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

so when I do that, the output list is duplicate[1,3]. I dont understand where are 12 and 34.

Answer 1

On this step duplicate.next=new Node(a); you every time overwrite previous value of duplicate.next. You should change reference on duplicate on every step when you create next node.

you can use recursion to create copy of the next node and create new node after that:

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

and without recursion:

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

If I understand you right, you need to create reverted list. In this case you don't need to create new copy of initial list.

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

to create reverse list with recursion, you just need additional method to keep a reference on previous created copy:

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