#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$[-] <[email protected]>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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
