Рекурсивно реверсивный связанный список

Question

Я пытаюсь изменить LinkedList с помощью рекурсивных вызовов, пожалуйста, дайте мне знать, где я ошибаюсь, я не могу поймать обратную голову LL. LLNode - это узел связанного списка, а ReverseLLRecursively.reverse - это функция, которую я написал для реверсирования.

Вот мой код:

public class LLNode { 
    private int data; 
    private LLNode next; 

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

    public int getData() { 
     return data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public LLNode getNext() { 
     return next; 
    } 

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

    @Override 
    public String toString() { 
     return data + "->[" + (next!=null?next.data:"") + "]"; 
    } 
} 

public class ReverseLLRecursively { 

    public static LLNode newHead = new LLNode(-1, null); 

    public static LLNode reverse(LLNode head, LLNode newHead) { 
     if(head==null || head.getNext()==null) { 
      newHead = head; 
      return head; 
     } 

     LLNode node = reverse(head.getNext(), newHead); 
     node.setNext(head); 
     head.setNext(null); 
     return node.getNext(); 
    } 

    public static void main(String[] args) { 
     LLNode ll = new LLNode(1,new LLNode(2, new LLNode(3, new LLNode(3, new LLNode(2, new LLNode(3, null)))))); 

     reverse(ll , newHead); 
     System.out.println(newHead); 

    } 

} 

Answer 1

Вы усложнять вашу проблему и работать с локальной переменной, которая имеет такое же имя, как статический член. Это должно быть проще:

public static LLNode reverse(LLNode previous) { 
    if(previous==null) { 
     return null; 
    } 
    LLNode toReturn = (previous->getNext() == null) ? previous : reverse(previous.getNext()); 
    previous.getNext().setNext(previous); 
    return toReturn; 
} 

Обратите внимание, что toReturn будет новой головой.

Answer 2

Выполнение обратного метода LLNode делает вещи несколько проще.

Вы хотите вернуть последнее значение (и только последнее) в свой список. Если у вас есть это, вернитесь, иначе пойдете глубже, пока не получите его. После того, как у вас есть конец, сохраните его, setNext, поскольку вам больше не нужно значение следующего, верните конец.

public LLNode reverse(LLNode previous) { 
    if(getNext()==null) { 
     setNext(previous); 
     return this; 
    } 
    LLNode returnValue = getNext().reverse(this); 
    setNext(previous); 
    return returnValue; 
} 

public static void main(String[] args) { 
     LLNode ll = new LLNode(1,new LLNode(2, new LLNode(3, new LLNode(3, new LLNode(2, new LLNode(3, null)))))); 

     ll = ll.reverse(null); 
     System.out.println(ll); 

} 

В противном случае статический вариант, если он вам нужен по какой-либо причине.

public static LLNode reverse(LLNode current) { 
    if(current.getNext()==null) { 
     return current; 
    } 
    LLNode returnValue = reverse(current.getNext()); 
    current.getNext().setNext(current); 
    current.setNext(null); 
    return returnValue; 
} 

public static void main(String[] args) { 
     LLNode ll = new LLNode(1,new LLNode(2, new LLNode(3, new LLNode(3, new LLNode(2, new LLNode(3, null)))))); 

     ll = reverse(ll); 
     System.out.println(ll); 

}