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

Question

Я искал код ниже из Стэнфордской библиотеки:

void recursiveReverse(struct node** head_ref)
{
    struct node* first;
    struct node* rest;

    /* empty list */
    if (*head_ref == NULL)
       return;  

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref;
    rest  = first->next;

    /* List has only one node */
    if (rest == NULL)
       return;  

    /* put the first element on the end of the list */
    recursiveReverse(&rest);
    first->next->next  = first; 

    /* tricky step -- see the diagram */
    first->next  = NULL;         

    /* fix the head pointer */
    *head_ref = rest;
}

Что я не понимаю, так это последний рекурсивный шаг, например, если список 1-2-3-4. Теперь для последнего рекурсивного шага первым будет 1, а остальным будет 2. Так что, если вы установите * head_ref = отдых .. что делает главу списка 2 ?? Может кто-нибудь объяснить, пожалуйста, как после обращения в начало списка становится 4 ??

Answer 1

Нарисуйте трассировку стека ...

Intial - {1,2,3,4}
Head - 1
Rest = 2,3,4
Recurse(2,3,4)
Head = 2
Rest = 3,4
Recurse(3,4)
Head = 3 
Rest = 4
Recurse (4)
Head = 4
Rest = null //Base Case Reached!! Unwind.

So now we pick up 
Recurse(3,4)
Head = 3 
Rest = 4
// Return picks up here
first->next->next  = first; 
so list is:
3,4,3
// set head to null,
null ,4,3,
//Off with his head!
4,3
Return

Now we're here
Recurse(2,3,4)
Head = 2
Rest = 3,4
Previous return leaves state as:
Head = 2  //But Head -> next is still 3! -- We haven't changed that yet..
Rest = 4,3  
Head->next is 3, 
Head->next->next = 2 makes the list (actually a tree now)
4->3->2
   ^
   |
   2
And chop off the head leaving
4->3->2
and return.

Similarly, do the last step which will leave
4->3->2->1
      ^
      |
      1
and chop off the head, which removes the one. 

Answer 2

Рассмотрим список:

   1  ->  2  ->  3  ->  4 -> NULL
   ^      ^
   |      |
 first   rest

Где first указывает на первый узел, а остальные указывают на узел рядом с first.

Поскольку список не пуст и список не содержит одного узла, мы делаем рекурсивный вызов reverse, чтобы перевернуть список, на который указывает rest. Вот как выглядит список после обращения к остальной части списка:

   1  ->  2  <-  3  <-  4
   ^      |             ^
   |     NULL           |
 first                 rest

Как видно, rest теперь указывает на перевернутый список, в котором 4 в начале и 2 в конце списка. Следующий указатель узла 2 - NULL.

Теперь нам нужно добавить первый узел в конец списка перевернутых остатков. Чтобы добавить что-либо в конец списка, нам нужен доступ к последнему узлу списка. В этом случае нам нужен доступ к последнему узлу списка перевернутых остатков. Посмотрите на диаграмму, first -> next указывает на последний перевернутый список остальных узлов. Следовательно, first -> next -> next будет следующим указателем последнего узла в списке обращенных остатков. Теперь нам нужно указать first, поэтому мы делаем:

first -> next -> next = first;

После этого шага список выглядит так:

   1  <-  2  <-  3  <-  4
   ^  ->                ^
   |                    |
 first                 rest

Теперь поле next последнего узла списка должно быть NULL. Но сейчас дело не в этом. Поле next последнего узла (узел 1) указывает на узел перед ним (узел 2). Чтобы это исправить мы делаем:

first -> next = NULL;

После этого список выглядит так:

NULL <- 1  <-  2  <-  3  <-  4
        ^                    ^
        |                    |
      first                 rest

Как видно, список теперь правильно перевернут, с rest, указывающим на заголовок перевернутого списка.

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

*head = rest;

Answer 3

Остальное не 2, а 2 -> 3 -> 4, которое рекурсивно меняется на противоположное. После этого мы устанавливаем *head_ref в rest, который теперь (рекурсивно изменен!) 4 -> 3 -> 2.

Важным моментом здесь является то, что хотя оба типа first и rest имеют одинаковый тип, то есть node*, они концептуально принципиально различаются: first указывает на один единственный элемент , тогда как rest указывает на связанный список элементов. Этот связанный список рекурсивно реверсируется, прежде чем он будет назначен на *head_ref.

Answer 4

Недавно я написал рекурсивный метод обращения к связанному списку в ruby. Вот оно:

def reverse!( node_1 = @head, node_2 = @head.link )
    unless node_2.link 
        node_2.link = node_1
        @head = node_2
        return node_1
    else 
        return_node = reverse!(node_1.link, node_2.link)
        return_node.link = node_1
        node_1.link = nil
        return node_1
    end
    return self
end