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

Я смотрел код ниже из библиотеки stanford:

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, а rest будет равно 2. Поэтому, если вы установите * head_ref = отдых.. что делает руководитель списка 2?? Может кто-нибудь объяснить, как после реверса глава списка становится 4??

Ответ 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.

Ответ 2

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

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

Где first указывает на первый node и отдыхает на node рядом с first.

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

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

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

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

first -> next -> next = first;

После этого шага список выглядит следующим образом:

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

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

first -> next = NULL;

После этого список выглядит следующим образом:

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

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

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

*head = rest;

Ответ 3

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

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

Ответ 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