Сторнирование связанного списка с использованием рекурсивного метода

Question

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

// Java program for reversing the linked list

class MyLinkedList {

    static Node head;

    static class Node {

        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    /* Function to reverse the linked list */
    Node reverse(Node node) {


          add content      


        node = prev;
        return node;
    }

    // prints content of double linked list
    void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        add content    }
}

Answer 1

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

Дано (1) -> (2) -> (3) ->

Инициализировать 3 переменные prev =ноль;cur = 1;next = 2;

Теперь, чтобы изменить это, начните с текущего узла, он должен указывать на предыдущий, но при этом мы теряем связь между 1 и 2. Чтобы сохранить связь следующей = 2. Теперьтекущая 1 теперь может указывать на предыдущее значение, т.е. cur.next = prev.

Так что теперь у нас есть <- (1) (2) -> (3) ->

Затемперейдите к следующей итерации, вам просто нужно обновить prev = cur и cur = next.

Повторяя это до тех пор, пока не достигнете нуля, связанный список обновляется таким образом.

<- (1) <- (2) (3) ->

<- (1) <- (2) <- (3) </p>

Так что это можно сделать с помощью цикла while, подобного этому

Node prev = null;
Node cur = node;
Node next;
while (cur != null) {
    next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return prev;

Теперь, чтобы сделать это с помощью рекурсии, вам просто нужно иметь 3 параметра, то есть prev, cur и next.Определите ваш базовый случай (что должна делать функция, когда она достигает нуля).Затем выполните 4 строки кода внутри цикла while, затем вызовите рекурсивную функцию.

Answer 2

Вместо «добавить контент» должно быть:

1. Помните узел, на который ссылается ваш следующий узел.
2. Присвойте полю следующий Узел значение вашего тока Узел.
3. Сделать следующий Узел текущий один.
4. Сделать узел из шага 1 следующим: next one.
5. GOTO 1

(A) -> (B) где A - это ток Узел, а B - следующий Узел.