Обратный рекурсивно связанный список в Java

Question

Я пытаюсь создать список обратных ссылок. Новый свежий список должен быть создан рекурсивно.

Я создаю первый узел в обратном списке, и я пытаюсь создать подсписку Next, у которого следующий элемент будет следующим.next и, наконец, назначить этот подсписчик рядом с узлом. Проблема в том, что следующий узел остается NIL, хотя я воссоздал его в цикле for.

Редактировать: Функция не должна меняться (добавлять аргументы), потому что на ней выполняются некоторые тесты.

class Node { 
    private Object item; 
    private Node next,current; 

    public Node(Object o, Node n) { 
     this.item = o; 
     this.next = n; 
    } 

    public Node(Node n) { 
    } 

    public static final Node NIL = new Node(Node.NIL, Node.NIL); 

    public Object getItem() { 
     return this.item; 
    } 

    public Node getNext() { 
     return this.next; 
    } 

    public void setItem(Object o) { 
     this.item = o; 
    } 

    public void setNext(Node n) { 
     this.next = n; 
    } 

    // this method returns the item with index number i 
    public Object nthItem(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p.item; 
     } 
     return null; 
    } 

    // this method returns the the next item of the node 
    public Node nthNext(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p.getNext(); 
     } 
     return null; 
    } 

    public Node nthNode(int i) { 
     Node p = this; 
     while (p!=null){ 
      for (int k=1;k<=i;k++){ 
       p=p.next; 
      } 
      return p; 
     } 
     return NIL; 
    } 

    public int length(){ 
     if (this == NIL) return 0; 
     else return 1 + next.length(); 
    } 

    public Node remove(Object o){ 
     Node p = this; 
     if (p == NIL) return NIL; 
     else if(p.item == o) { 
      p = p.next; 
      return p.remove(o); 
     } 
     else return new Node(p.item, p.next.remove(o)); 
    } 

    public Node reverse() { 
     int i = this.length()-1; 
     if(this == NIL) return NIL; 

     Node node = new Node(Node.NIL, Node.NIL); 

     Node next = NIL; 

     //create the first node in the reversed list 
     if(i >= 1) node = new Node(nthItem(i), next); 
     else node = new Node(nthItem(i), Node.NIL); 

     //iterate through the original list and create a next node 
     if (i>0) { 
      for (int k=i; k>=0; k--){ 
       if (k<=0) { 
        next = NIL; 
       } 
       else { 
        next = new Node(nthItem(k-1),next); 
       }    
      } 
     } 

     //debugging in console 
     System.out.println("final node = " + next.item+" "); 
     return node; 
    } 
} 

class Test{ 

    public static void main(String[] string){ 
     Node n = new Node(1, Node.NIL); 
     Node nn = new Node(2, n); 

     Node r = nn.reverse(); 

     System.out.println("\t item " + r.getItem()+ " " + r.getNext().getItem() + " length " + r.length()); 
    } 
} 

Answer 1

Этот вопрос предназначен для проверки того, понимаете ли вы неявный стек. Каждый раз, когда вы делаете рекурсивный вызов, вы добавляете фрейм стека, поэтому рассматривайте стек так, как если бы вы выполняли процедуру итеративно.

Чтобы изменить список:

1. стека все элементы в порядке
2. сделать новый список, выталкивая каждый элемент.

Теперь преобразовать это рекурсивный вызов

//in [1,2,3,null] 
Node reverse(Node n){ 

    //base case 
    if(n == null) 
    { 
     return null; 
    } 

    // returns [null,3,2,1] 
    Node next = reverse(n.getNext()); 
    next.setNext(n);// set the next nodes next to its previous(n on unwinding) 
    return n; 
} 

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

Node oldHead = n; 
Node newHead = tail(n); 
oldHead.reverse();