реверсирование односвязного списка рекурсией

Question

Это код для обращения односвязного списка с помощью рекурсии:

public static LinkedListNode reverse_recursive(
      LinkedListNode head) {

    if (head == null || 
        head.next == null) {
        return head;
    }

    LinkedListNode reversed_list = 
      reverse_recursive(head.next);

    head.next.next = head;
    head.next = null;
    return reversed_list;
  }

Я знаю, что рекурсия не лучший способ решить эту проблему, но я не могу понять, что за код "head.next.next = head "делает.Я в замешательстве, пожалуйста, помогите мне очистить мой разум.Спасибо!

Answer 1

head.next.next = head 

назначает текущий узел (заголовок) в качестве ссылки узла, который был последний раз посещен рекурсией.

Рекурсия начинается с последнего узла в списке и заканчивается напервый узел.

Предполагая, что у вас есть связанный список A --> B --> C --> D --> NULL

Он начнет реверсировать вышеупомянутый список с node D, и поскольку узел D next равен null,рекурсия сразу же переместится на следующий узел, node C

Что произойдет, если она возьмет голову (которая теперь node C) и присвоит node D 's next

Это будет происходить до тех пор, пока не останется больше узлов для перемещения

Answer 2

public static LinkedListNode reverse_recursive(LinkedListNode head) {
if (head == null || head.next == null) {
    return head;
}

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

LinkedListNode reversed_list = reverse_recursive(head.next);

Мы отправляем следующий узел в рекурсивную функцию, например, если в нашем списке три узла 1-> 2-> 3, тогда мы будем отправлять второй узелв reverse_recursive функцию.Функция вернет 3-> 2, а reversed_list будет указывать на узел 3. И теперь нам нужно соединить узел 1 с обратным списком 3-> 2.

head.next.next = head;

head.next (узел 2) будетуказывает на (head.next.next) узел 1 (head).

head.next = null;

Поскольку узел 1 является последним узлом, он должен указывать на ноль, что означает, что больше нет узлов.

return reversed_list;

И теперь нам нужно только вернуть правильную ссылку (первый узел обратного списка).

Answer 3

head --> A
         .next --> B
                   .next --> C

Итак, в приведенном выше примере head.next ссылается на узел B, а head.next.next ссылается на узел C.

head.next.next = something

, таким образом, является эквивалентом

nodeB.next = something

В вашем коде something равно head.И head ссылается на узел A. Таким образом, он присваивает новое значение следующему узлу узла B, и это новое значение, если узел A:

head --> A <---------------
         .next --> B      |
                   .next --

Следующая инструкция

head.next = null, which thus leads to

head --> A <---------------
                   B      |
                   .next --