function to reverse a linked list using recursion in c++

Question

I have to write a function to reverse a linked list using recursion in C++. I did it and the reasoning seems correct to me, but the code is not working. Could someone explain me why? Thank you all!

This is the function:

list* reverseList(list* head, list* p, list* n){

    if(head->next == NULL){
        head->next = p;
        p = head;
        head = n;
        n = NULL;
        return head;
    }

    else{
        head->next = p;
        p = head;
        head = n;
        n = n->next;
        return reverseList(head, p, n);
    }

}

This is the list struct:

struct list{
    int val;
    list *next;
};

This is the main:

int main() {
    list *head, *p1, *p2, *prev, *next;

    head = new list;
    head->val = 1;
    p1 = new_node(head, 2);
    p2 = new_node(p1, 3);
    p2->next = NULL;
    print_list(head);

    prev = NULL;
    next = head->next;

    reverseList(head, prev, next);
    print_list(head);

    return 0;
}

And these are other functions i use to create new nodes with values and to print the list:

list* new_node(list* old_node, int value)
{
    old_node->next = new list;
    old_node->next->val = value;
    return old_node->next;
}

void print_list(list* head){
    while(head != NULL){
        cout << head->val << endl;
        head = head->next;
    }
}

You should add that main and post a snip-it that can be copied, compiled and run. How to create a Minimal, Complete, and Verifiable example — lakeweb
– lakeweb, Commented Feb 8, 2020 at 15:40
Add complete code so we can compile and see the result. Hint: *p is a pointer but p is just a local to function won't make any changes at calling function — TruthSeeker
– TruthSeeker, Commented Feb 8, 2020 at 16:06
Just traverse untill linked list is null, and when function retrun your last value is in stack and you can print or store the value in some array or something if(p->next == null) cout << p->data else p=p->next; p is pointer to a list — Kanishk Tanwar
– Kanishk Tanwar, Commented Feb 8, 2020 at 16:29
It seems to work, what you need to do is print_list(p2); The head is no longer the head after you reverse it. ` — lakeweb
– lakeweb, Commented Feb 8, 2020 at 16:43

TruthSeeker · Accepted Answer · 2020-02-08 17:33:24Z

1

There are two issues with your code,

Return value of reverseList is not collected and it should be head = reverseList(head, prev, next);
Inside reverseList on head->next == NULL you need to return previous pointer rather next pointer which is anyhow pointing to NULL.

list* reverseList(list* head, list* p, list* n) {
    if (head->next == NULL) {
        head->next = p;
        return head;
    }
    else {
        head->next = p;
        p = head;
        head = n;
        n = n->next;
        return reverseList(head, p, n);
    }
}

which can even be simplified to,

void reverseList(list* &head, list* &p) {
    if (!head) return;
    list* t = head->next;
    head->next = p;
    p = head;
    if (t)
    {
        head = t;
        reverseList(head, p);
    }
}

and called like reverseList(head, prev);

answered Feb 8, 2020 at 17:33

TruthSeeker

1,60912 silver badges24 bronze badges

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

Collectives™ on Stack Overflow

function to reverse a linked list using recursion in c++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related