CODEWITHSUNDEEP
c++recursionlinked-list
zupus
zupus

Reputation: 79

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

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;
    }
}

Upvotes: 0

Views: 159

Answers (1)

TruthSeeker
TruthSeeker

Reputation: 1579

There are two issues with your code,

  1. Return value of reverseList is not collected and it should be head = reverseList(head, prev, next);
  2. 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);

Upvotes: 1

Related Questions