Problems using recursion to reverse a linked list

Question

I am requested to write a driver function to call a recursive function. I was wondering what i need to do in the driver function.

this program is to reverse a linked list.

void invert_r()
{
    //This is the driver function for recursive_invert

    nodeType<Type> *p, *q;

    q = first;
    p = first;
    recursive_invert(q, p);
}
nodeType<Type>* recursive_invert(nodeType<Type> *q, nodeType<Type> *p)
{
    //Invert a linked list using recursion.
    //DO NOT create any new node in your implementation
    if(p -> link == NULL)
    {   
        q -> link = p;
        return p;
    }
    else
    {
        recursive_invert(p -> link, q) -> link = p;
    }
    return p;
}

Hard to say as long we can't see what first is. Otherwise everything looks fine. What specific problems do you get with this code? — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Oct 22, 2013 at 14:21
@g-makulik "first" is the first element of the linked list. i am confused about the use of driver function and how to use it and then call my recursive function... — Ruka Tsoi
– Ruka Tsoi, Commented Oct 22, 2013 at 14:22
the output of the function is that firstly reverse the linked list by iterative method. and then convert back the linked list by implementing the invert_r() to call the recursive one — Ruka Tsoi
– Ruka Tsoi, Commented Oct 22, 2013 at 14:24
If first is the first element of the linked list I think they have to be members of nodeType, so initialization on invert_r function should be made like this: q = q->first; — Lolito
– Lolito, Commented Oct 22, 2013 at 14:33
Since you need to pass (a pointer to) one node and (a pointer to) the next node, you need nodeType<Type> *p = first; nodeType<Type> *q = p->link; and probably first = recursive_invert(p, q);, don't you? At the least, you should not casually discard the return value from the recursive function since it is now the head of the list (and if you lose it, you won't be able to get to the start of the list again). — Jonathan Leffler
– Jonathan Leffler, Commented Oct 22, 2013 at 16:42

Anuj Garg · Accepted Answer · 2014-12-10 19:48:58Z

1

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;   

    /* reverse the rest list and put the first element at the end */
    recursiveReverse(&rest);
    first->next->next  = first;  

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

    /* fix the head pointer */
    *head_ref = rest;              
}

answered Dec 10, 2014 at 19:48

Anuj Garg

5927 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

John Kugelman Over a year ago

Your code doesn't look anything like the OP's code. It's got a different signature and different structure members.

Anuj Garg Over a year ago

John it is only for illustration purpose as like an Algo.

Andrew Barber Over a year ago

Please note that we expect answers to address the specific issues in the question. If you have a very relevant alternative, you can consider adding that - but please be sure to address the question and explain exactly why, first.

Uli Köhler Over a year ago

Some explanation would be nice, but if you'd add that I think it might be a good answer ;-)

Collectives™ on Stack Overflow

Problems using recursion to reverse a linked list

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related