Reverse a linked list recursive solution -C

Question

I wanna to write a function in C to reverse Linked list by recursion, however I see many ways as iterative way (which done with me) .. But in recursive way the function always return 0

Revers Linked List Code

node * r_reverseItem(node * head) {    
    if (head == NULL) //only one elem
        return NULL;

    node * currentNode = head;

    if(currentNode->next == NULL) { 
        //set HEAD to current TAIL since we are reversing list
        head = currentNode; 
        return head; //since this is the base case
    }

    r_reverseItem(currentNode->next);
    currentNode->next->next = currentNode;
    currentNode->next = NULL; //set "old" next pointer to NULL
}

So, what is the problem here in this code please? however, any useful examples or sites are also desirable.

EDIT

Just simply I know where is my fault. I forgot to add a return statement which (killer mistake). So the correct function as below:

   node * r_reverseItem(node * head) {    
    if (head == NULL) //only one elem
        return NULL;

    node * currentNode = head;

    if(currentNode->next == NULL) { 
        //set HEAD to current TAIL since we are reversing list
        head = currentNode; 
        return head; //since this is the base case
    }

       node * newNode =r_reverseItem(currentNode->next);
           currentNode->next->next = currentNode;
           currentNode->next = NULL; //set "old" next pointer to NULL
           return newNode;
}

Well, first this doesn't look right: if (head == NULL) //only one elem. If head is NULL, then you have zero elements. — jedison
– jedison, Commented Apr 29, 2014 at 12:15
what do you mean by that please? I sent a list with 1,2,3,4 items So it is not empty! I do not know where is the error here to print 0 — Maheera Jazi
– Maheera Jazi, Commented Apr 29, 2014 at 12:16
"recursive way the function always return 0" Sometimes it returns an undefined value, too, because return is not reached. Can you spot that place? — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Apr 29, 2014 at 12:18
yes please, I am one who understand slowly, so what do you mean? I add return statement already in base case of recursion ?! — Maheera Jazi
– Maheera Jazi, Commented Apr 29, 2014 at 12:20
I suggest you return it from your function. Notice that your function has a return value that is not assigned to anything. — o_weisman
– o_weisman, Commented Apr 29, 2014 at 12:34

Community · Accepted Answer · 2017-05-23 10:26:05Z

2

Original solution implemented in Java , i only translated it to C with your variable names

node* r_reverseItem(node * head)
{
    if( !head )   // empty list
        return NULL;

    if( !(head->next) ) //last element becomes the head of the reversed list
        return head;

    node *currentNode = head->next; //preserve next element
    head->next = NULL;

        node* newHead = r_reverseItem(currentNode);

    currentNode->next = head; 
    return newHead; //once you have head you don't change it 
}

edited May 23, 2017 at 10:26

CommunityBot

11 silver badge

answered Apr 29, 2014 at 13:53

Dabo

2,3832 gold badges21 silver badges30 bronze badges

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

2 Comments

Maheera Jazi Over a year ago

thanks really for your answer, BUT what does that line mean please return newHead; and for what we must use it? ok I have a big gab I must work on it to understand well the linked list! :(

Dabo Over a year ago

you understand that you actually creating a new list, so you will have to return the head of this new list, right ? And as the list you trying to create is the reverse of the original the head of the new list is the tail of the original one. There is no use of it inside r_reverseItem, you only need it to have acces to the list after the function is done.

user3551374 · Accepted Answer · 2014-04-29 19:03:17Z

1

Check this web site , basically it explain three way of reverse a link list with example after you read them you will be able to made it recursively as you want

http://www.codeproject.com/Articles/27742/How-To-Reverse-a-Linked-List-Different-Ways

answered Apr 29, 2014 at 19:03

user3551374

111 bronze badge

Collectives™ on Stack Overflow

Reverse a linked list recursive solution -C

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related