Рекурсивных Связанного список реверс

Question

создал связанный список классы для проекта Java и нужен способ, чтобы полностью изменить список, чтобы мой друг, и я в конце концов придумал следующий рекурсивный метод, и это вспомогательный метод:

(только для осветления , first является переменным экземпляр первого узла в списке)

public void reverse() 
{ 
    first = reverse(first); 
} 

public Node reverse(Node in) 
{ 
    if (in == null || in.next == null) 
    { 
     return in; 
    } 

     Node next = in.next; 
     in.next = null; 
     Node rest = reverse(next); 
     next.next = in; 
     return rest; 
} 

Когда узлы содержат целые числа, и мы вход 1, 2 и 3 в начале списка (они становятся 3, 2, 1, когда добавлен как первый узел), а затем попытайтесь отменить 3, 2, 1, чтобы стать 1, 2, 3, эта функция работает так, как планировалось.

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

Например, когда я проследить функцию (3, 2, 1) оказывается, что:

next = in.next (который 2, 1) получает передается снова, пока это не только (1), а затем, что получает прошло назад в rest. Но после того, как рекурсия состоится, на самом деле ничего не происходит с rest. Это происходит с next.next, и я не могу понять, как next.next влияет на rest в любом случае.

Я не могу показаться, чтобы найти точки, в которых rest идет от (1) к (1,2) в (1,2,3) во время барботирования обратно.

Если кто-нибудь может помочь объяснить более подробно, как эта функция изменяет rest, было бы здорово. Я проследил эту функцию почти 20 или около того раз, пытаясь понять, и что-то происходит, что я просто не вижу.

Я даже взял его у своего учителя, и он дал мне ответ BS, эквивалентный «Если он работает, то он работает, это рекурсия, не пытайтесь понять это». - Что это за совет?

Thanks

Answer 1

Попробуйте составить список с двумя узлами в нем. Это самый простой пример.

first --> [A] -> [B] -> null 

Мы призываем reverse(first), а так A не является нулевым, мы приводим в следующих назначениях:

in = A 
next = B 

Мы разорвать связь между А и В на этом шаге:

in.next = null; 

Итак, у нас есть:

first --> [A] [B] -> null 

Теперь мы хотим, чтобы остальные, которые назначены на рекурсивный вызов этой функции, вместо B. Мы повторяем шаги теперь с B, но так как B.next имеет значение null, мы остаемся только с B.

Итак, мы получаем B обратно в результате rest. Теперь мы назначим next.next на in, что означает, что B.next теперь A.

[B] -> [A] -> null 
     ^
     first 

Вернемся rest назад к кому назвала его, что в этом случае приводит к присвоению first.

first --> [B] -> [A] -> null 

... и теперь список отменен.

Это общая неисправность; взгляните на это с тремя узлами, и вы увидите немного больше поведения. Помните: каждый рекурсивный вызов создает новые переменные для in и next, а те, которые существовали ранее, откладываются до тех пор, пока мы не вернемся к этому конкретному методу.