обратный список без удаления начального списка

Question

Я пытаюсь изменить список, но хочу сохранить свой первоначальный список. Моя функция обратного не сохраняет первоначальный список

Например, я хочу, чтобы изменить это:

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

и моя функция:

public Node reverse(){ 

    Node p= this; 
    if(p == NIL) 
     return Node.NIL; 


    if(p.n == Node.NIL) 
     return p; 

    Node rest = p.getNext(); 
    p.setNext(Node.NIL); 
    Node reverseRest = rest.reverse(); 

    rest.setNext(p); 
    return reverseRest; 
} 

Длина моего старого списка после реверса равно 1, и я хочу, чтобы для этого примера было 4. Мой старый и мой новый список должен иметь одинаковую длину после обратного.

Answer 1

Для того, чтобы сохранить первоначальный список вашего метод reverseдолжен создавать новые Nodes объектов, а не внесение изменений в уже существующие.

Если вы хотите написать рекурсивную reverse(), который не принимает никаких параметров, вы можете сделать это следующим образом:

• Создайте новый Node и копировать содержимое этого узла в него; установить next в NIL
• Если следующие из этого узла NIL, возвращает результат предыдущего шага
• В противном случае, вызов reverse() на следующем
• Возьмите возвращаемое значение из предыдущего вызова, и перейдите к его концу
• Добавьте новый узел с первого шага в конец и верните результат.

Лучшим подходом является изменение подписи reverse для создания узлов, созданных до сих пор, в обратном порядке. Это создаст алгоритм O (n), а немодифицированный алгоритм выше O (n).

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 rest = new Node(); 
       rest = firstDuplicate.getNext(); 

       firstDuplicate.setNext(Node.NIL); 

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

       /* Join the two lists */ 
       rest.setNext(firstDuplicate); 
       return reverseRest; 
      } 
} 

Я попытался дублировать свой первоначальный список и работать над дублирующим, чтобы сохранить оригинал. но это худший

Answer 3

Это рекурсивная реализация на основе dasblinkenlight (в любовь ручки!) предложение: «Лучший подход, чтобы изменить подпись реверсе принять узлы, созданные до сих пор, в обратном порядке»

public class Node { 
    private static final Node NIL=null; 

    public Node(int data, Node next) { 
     super(); 
     this.data = data; 
     this.next = next; 
    } 

    public int getData() { 
     return data; 
    } 

    public Node getNext() { 
     return next; 
    } 

    private int data; 

    private Node next; 

    public String toString() 
    { 
     String s = ""; 
     Node cur = this; 
     while (cur != Node.NIL) { 
      s += cur.data + ","; 
      cur = cur.getNext(); 
     } 
     return s; 
    } 

    /* Where the recursive magic happens */ 
    /* build the reversed list in the parameter 'reversed' */ 
    public Node reverse(Node n, Node reversed) 
    { 
     if (n == Node.NIL) { 
      return reversed; 
     } else { 
      return reverse(n.next,new Node(n.data,reversed)); 
     } 
    } 

    /* Kick off the recursion from the head node */ 
    public Node reverseList() { 
     return reverse(this,Node.NIL); 
    } 

    public static void main (String args[]) { 

     // Create a sample list 
     Node n = new Node(1,new Node(12, new Node(34, new Node(3, Node.NIL)))); 

     System.out.println(n); 
     System.out.println(n.reverseList()); 
    } 

}