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

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??

16

c algorithm recursion linked-list reverse

задан codaddict 25 February 2011 в 09:08

2 ответа

Другие вопросы по тегам:

c algorithm recursion linked-list reverse

Похожие вопросы:

score 21 · 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.

score 7 · Answer 2

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

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