current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

I was trying to reverse the link list using recursion and somehow I did it?

But one think is bothering me how the head in the last line finally points to the element 4 (i.e. the first element after reversing the link list if (1,2,3,4) was the initial link list?

What I am thinking it is still pointing to 2 after the reverse got complete but my programe is running correctly ? that sucks me?

Or am I logically wrong somewhere?

void Reverse(struct node* head)
{
struct node* f;
struct node* r;

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

/* suppose f = {1, 2, 3}, r = {2, 3} */
f = *head;
r  = f->next;

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

/* put the f element on the end of the list */
Reverse(&r);
f->next->next  = f; 

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

/* fix the head pointer */
*head = r;
}
share|improve this question

closed as off topic by Jerry Coffin, Jeff Vanzella, Winston Ewert Sep 13 '12 at 22:50

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.
2  
Shouldn't argument to your function be pointer to a pointer (struct node **head)? –  Krzysztof Adamski Sep 13 '12 at 20:08
    
Works: Just fix the declaration Reverse(struct node** head). –  Loki Astari Sep 13 '12 at 20:23
    
Somewhat regretfully voting to close -- at least as I understand the charter, this site is intended for reviews of working code, but this seems to need a fair amount of work before it'll even compile. –  Jerry Coffin Sep 13 '12 at 20:36
    
Trying to understand code is off-topic on this site. –  Winston Ewert Sep 13 '12 at 22:50

2 Answers 2

up vote 1 down vote

This program looks correct to me. f is set to be the last node in the list by setting f->next->next = f (i.e f->next used to be the second node (2), but the second node was moved to the end of the list in the recursion step, so it is now the last node: (4, 3, 2). So f is set to be the node after the last, which is correct: (4, 3, 2, 1). Because f is now the last node, f->next must be set to NULL to indicate the end of the list. r was updated by the recursion step as well and now points to the beginning of the reversed rest of the list (4), so the element which used to be the last in the list is now the first element. It is then set to be the head element of the whole reversed list.

share|improve this answer
up vote 1 down vote

You have to analize your recursion in backward way as you are doing changes after calling the funtion. So the last call will actually do it's changes first. Now in your last call, r points to the last element of the list and you update *head (which is r in calling funtion) to it. This means that when next function returns it will too update head to last element on the list.

So each time you call *head = r, r points to the last element. This is why at the end of execution, head points to the right element.

Consider this simplification of how your function is called. I'm using r0,r1,r2 and r3 to show you that their are r value at nth level of recursion. *X is address of X.

r0=*1;
Reverse({1,2,3,4} {
  r1=*2;
  Reverse({2,3,4} {
    r2=*3;
    Revers({3,4}) {
      r3=*4;
      Reverse({2}) <- this one is not interesting as nothing happens
      r2=r3;
    }
    r1=r2;
  }
  r0=r1;
}

So at first r0 holds address of element 1. But Reverse function will update it as its last step to value of r1. But r1 will be updated to the value of r2 which in turn will have value of r3 which points to the last element. This is why at the end, r0 points to last element of the list too.

share|improve this answer

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