#include<stdio.h> typedef struct ll { int data; struct ll *link; }node;
node *nw,*next,*prev=NULL,*head,*temp,*head1; void print(node *temp) { while(temp!=NULL) { printf("%d\n",temp->data); temp=temp->link; } } void print_reverse(node *temp) { if(temp!=NULL) { print_reverse(temp->link); printf("%d",temp->data); } else return; } node* recursive_reverse(node *temp) { if(temp->link==NULL) { head1=temp; return temp; } return (recursive_reverse(temp->link)->link=temp); if(head==temp) { head->link=NULL; head=head1; } } main() { int i,n; scanf("%d",&n); head=(node*)malloc(sizeof(node)); head->data=n; head->link=NULL; prev=head; for(i=0;i<4;i++) { scanf("%d",&n); nw=(node*)malloc(sizeof(node)); nw->data=n; nw->link=NULL; prev->link=nw; prev=nw; } print(head); print_reverse(head); recursive_reverse(head); print(head); } ...hi my code works fine , except for when i call that " recursive_reverse()" function it goes into infinite loop.....i have implemented using "global head" .... ....can anybody please tell me where i have gone wrong....thanks :) On Mon, May 9, 2011 at 9:25 PM, LOKE$[-] <sripathi.karth...@gmail.com>wrote: > hi > > Guys reversing the linked list is a very important question. > It involves little trick in it. > Many peoples had a trouble in finding it out. > > In recursion, > there are two ways > 1.with global head, > 2.returning head. > > I putting the code here for the first approach. > > node *head; > > node* recurse_reverse_with_global_head(node *root) > { > if(root->next!=NULL) > { > node *dd = root->next; > root->next= NULL; > recurse_reverse_with_global_head(dd)->next = root; > return(root); > } > else > { > head=root; > return head; > } > } > > main() > { > recurse_reverse_with_global_head( head ); > print(); > } > > see in this note the following points cleanly. > Its is very important > 1. am putting head as global pointer. > 2. while traversing towards the end, am changing the current nodes > link to next as null. > 3. traversing from the next. > 4. before clearing am using dummy node for storing the next postion, > using dummy am traversing > 5. am storing the head in the nodes next that is returning from the > recursion. > 6. ***** when recursion reaches end returning root. > 7 ******* storing the last node in the global head. > > Last point is the trick here, > if you give this solution, they will ask you not to use global head. > > so follow this approach, > > node *recurse_reverse_without_global_head(node *root,node *next) > { > node *ret = NULL; > if ( root == NULL ) > return NULL; > else if ( root->next != NULL ) > { > ret = recurse_reverse_without_global_head(root->next,root); > } > else if ( root->next == NULL ) > { > ret = root; > } > > root->next = next; > return ret; > > } > > main() > { > node *dummy = NULL; > head = recurse_reverse_without_global_head( head , dummy ); > print(); > > } > > in this code > 1. using two pointers one for the current , another previous, > 2. while reversing current->next will become previous. current->next = > previous. > 3. am passing the null pointer as next pointer, this is because in > reversing head->next have to be Null. > 4. in passing to next recursion an forwarding the current(root) > pointer to current(root)->next , putting current(root) pointer in the > next. > 5. ********at the end ie root->next == NULL, am storing the last node > in the ret, which will be safely carried to trace back the recursion, > and it will return last node in the main. > 6. before that just change the link current->next = next. > > > guys it is becoming a serious interview quesiton. Many peoples falling in > to it. > do remember it. i suggest to memorize this five lines of code, since > it will be used as utility function for other problems. > > if you don''t tell this answer they think that "he/she doesn't know > even a link list reversal, a basic one.........." . > it will create bad impression on you. > mind this question. > write it in your placement note, while going for the interview, have a > look at it once, before starting your interview. > > > > > -- > endrum anbudan > G V Navin. > > -- Regards, $iva -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.