Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 2 down vote favorite

I am studying for an exam with Linked Lists in C. I found myself a "reviewer" it had this snippet of code. For the life of me, I cannot understand how the rest is reversed. Here it is... it is from Linked List Problems by Mr.Nick Parlante (taken CIS Library, Stanford). I will put in Mr. Nick's Comments.

RecursiveReverse() Solution

Probably the hardest part is accepting the concept that the RecursiveReverse(&rest) does in fact reverse the rest. Then then there's a trick to getting the one front node all the way to the end of the list. Make a drawing to see how the trick works.

void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                         // after: rest = {3, 2}
first->next->next = first; // put the first elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer

}

I've made countless drawings in attempts to trace what is going on, and I just cannot understand how RecursiveRest(&rest) actually reverses the rest. Please help. I am getting quite frustrated. What I end up getting is smaller "rest"s..and nothing is reversed. Thank you so much in advance.

share|improve this question

2 Answers

up vote 5 down vote

Recursion is usually hard to comprehend because it's hard to see how it decomposes into basic steps.

It is usually easier to think of the recursive part as already finished and only reason about the combination step (this is most useful when designing the algorithm).

When you are trying to visualize how an recursive algorithm works you have to keep in mind that there are two processes at work:

  • the decomposition of the original problem in smaller problems until you find the termination case
  • the solving of the termination case
  • the combination of the results.

It's like a two way street. First you go one way until the end case while breaking up the problem. You then solve the end case. After that you return at the beginning while combining the partial results.

For your case it might go like this. Note that [A-B] means a list.

[A-B-C-D-E] // RecursiveReverse([A, B, C, D, E])
(A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E])
(A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E])
(A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E])
(A (B (C (D [E])))) // this means we are calling RecursiveReverse([E]) 
                    // hit the end case and solve it trivially
(A (B (C (D [E])))) // solved
(A (B (C [E-D]))) // and go back while applying the combination case
(A (B [E-D-C])) // combine
(A [E-D-C-B]) // combine
[E-D-C-B-A] // combine

Hope this helps.

share|improve this answer
Excellent graphic :) – sarnold Jan 24 '11 at 8:31
@sarnold Thanks :). I try to be a little helpful :). – Mihai Claudiu Toader Jan 24 '11 at 9:05
Thank you very much, Sir! I understood it already. – Scared Jan 24 '11 at 9:56
@camilla you're welcome :) – Mihai Claudiu Toader Jan 24 '11 at 10:05
up vote 1 down vote
  1. At each step the code remembers the current and the next node (first and rest).
  2. Assume that RecursiveReverse(&rest) works and reverses the remaining list.
  3. Then the rest node will be at the last position when the call returns. So you just have to check the last three lines of code.
  4. You will see that rest is changed to point at first (first->next->next = first), and first points to NULL (first->next = NULL), i.e. you move first to the end of the list.
share|improve this answer
Thank you very much. This really helped and I understand what is going on now. :) – Scared Jan 24 '11 at 9:56
You are welcome! – George Jan 24 '11 at 11:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.