CODEWITHSUNDEEP
c++linked-listpass-by-reference
Tony Tarng
Tony Tarng

Reputation: 749

How to reverse a linked list using one pass by reference variable?

I'm trying to reverse a linked list using recursion (not iteratively). Originally, I set my head pointer as a global variable so I don't need to return head. This version works fine, so I want to implement a version that takes head as a local variable. The code is as below:

void Reverse(node* &head, node *p)
{
    if(p == NULL) return; //nothing in list
    if(p->link == NULL)
    {
        head = p;
        return;
    }
    Reverse(head, p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
}
//some code to set local var head to a linked list
Reverse(head, head);

It works fine, but it seems so cumbersome. I have tried some ways to do it with just one variable but it doesn't work. 

void Reverse(node* &head)
{
    if(head == NULL) return;
    node *p = head;
    if(p->link == NULL)
    {
        head = p;
        return;
    }
    Reverse(p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
}
//some code to set local var head to a linked list
Reverse(head);
Print(head); //output only last element in list

Is there any other way to implement it with just one pass by reference variable? Also, could you explain why the 2nd code outputs like it does? Thanks!Edit: So it seems that this isn't such a good way to do it. So the last approach I can think of is to take a pass by value parameter and return the result(assuming head is local). I tried implementing it as such:

node* Reverse(node *p)
{
    if(p == NULL) return p; //nothing in list
    if(p->link == NULL)
    {
        return p;
    }
    Reverse(p->link);
    node *q = p->link;
    q->link = p;
    p->link = NULL;
    //control may reach end of non-void fucntion
}

but I can't think of a way to get around the "control may reach end of non-void function" problem. Any help?

Upvotes: 0

Views: 622

Answers (1)

yizzlez
yizzlez

Reputation: 8805

An easy solution: you can just call your first function in Reverse:

void Reverse(node *&head) {
    Reverse(head, head); //may want to rename or make private
}

Upvotes: 1

Related Questions