CODEWITHSUNDEEP
c++listc++11recursion
Deepanshu Bansal
Deepanshu Bansal

Reputation: 21

reverse linked list using recursion

I am trying to reverse a linked list using recursion. I made the reverse() function to reverse the list. I created a linked list in main() and also defined print() method. I don't know what mistake I am making. Please help me correct it. The code snippets are given below.

struct node
{
    int data;
    struct node *next;
}*head;

void reverse(node **firstnode,node *n)
{
    if(n==NULL)
    {
        head=n;
        return;
    }
    reverse(&head,n->next);
    struct node *q=n->next;
    n->next=q;
    q->next=NULL;
}

void main()
{
    ......

    head=first;
    reverse(&first,first);
    print(head);
}

Upvotes: 0

Views: 864

Answers (4)

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

Since you want to understand the code, and you have several great resources with finished code already, more finished code examples aren't needed. I'll just answer with some concepts and point you at the errors you need to fix.

First, some background concepts.

Linked lists: first and rest

Any linked list is either empty, or can be broken down into first (a node) and rest (a smaller linked list, or empty). This makes recursion much easier.

if (head){
    node * first = head;
    node * rest  = head->next;
}

Invariant (simplified): A guarantee that is always true at the start and end of your function.

In a linked list, you expect that head points to a node, which points to another node, and so forth, until you get to the end, which is signaled by a nullptr. All of the nodes are different. All of the nodes are valid. These are the guarantees that must be true before you call your function and when your function returns.

In a recursive function, the invariants must hold on the sublist you are reversing at every step, because you return from the function at every step. But this makes recursion much easier because all you have to do is make sure that if the input is good, then your function will return a good value at the current step.

End of recursion: You can prove that your recursive function never gets in an infinite loop by combining the previous concepts. If the invariants hold, then each step will work, and because each recursive call will take rest, which is guaranteed to be either nullptr or a shorter list, eventually we have to reach the end. And of course show that you handle the end.

Okay, on to the actual problems:

You don't handle end of recursion correctly. You just set head=nullptr at the end, and I'm pretty sure that's not what you want for head. You may want to handle the end if (nullptr == n->next), because then you know that is the last node. Of course, you still have to correctly handle the trivial case where nullptr==head.

You don't preserve invariants. You tried, but it looks like your bookkeeping is just all wrong. I suggest using the debugger or 3x5 notecards to step through what you're actually doing to fix the actual work of swapping things around. For example, it looks like you just confused which node is which in this code snippet:

struct node *q=n->next;   // n is first, q is rest
// what if nullptr == q?
n->next=q;                // n->next = n->next doesn't actually change anything
q->next=NULL;             // this must already be true if reverse(rest) did its job
// q and n were swapped?

Also, your function takes "firstnode" but does not use it, but instead sets the global variable "head" as a side effect.

Upvotes: 0

Archit Garg
Archit Garg

Reputation: 1012

List* recur_rlist(List* head)
{
    List* result;
    if(!(head && head->next)) 
        return head;

    result = recur_rlist(head->next);
    head->next->next = head;
    head->next = NULL;

    return result;
}

void printList(List* head)
{
    while(head != NULL) {
        std::cout<<head->data<<" ";
        head = head->next;
    }
}
void main()
{
    List* list = createNode(2);
    append(list, createNode(3));
    append(list, createNode(4));
    append(list, createNode(5));
    append(list, createNode(6));
    List* revlist = recur_rlist(list);
    printList(revlist);
}

Upvotes: 1

pthomaid
pthomaid

Reputation: 177

I think you mixed up your addressing at the end of the reverse function, it should probably look like:

q->next=n;
n->next=NULL;

Also, I am not sure if you need the "firstnode" argument.

Upvotes: 0

Humam Helfawi
Humam Helfawi

Reputation: 20264

It may not address your question directly. However, you mentioned C++11 in the tags. So, take look at std::forward_list. It is a standard container that is based on single linked-list.

Upvotes: 1

Related Questions