Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Reversing a linkedlist recursively in c

Tags:

The following code works fine when head is sent as a parameter to it. As I am new to C, I couldn't understand how it works. Help me out please.

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

I dont know how the links are provided using those recursive calls. ie) if the links are as,

1 -> 2 -> 3 -> 4 

then hw is it changed as,

4 -> 3 -> 2 -> 1
like image 637
rampireram Avatar asked Dec 29 '12 10:12

rampireram


People also ask

What is reverse linked list in C?

Reverse linked list is a linked list created to form a linked list by reversing the links of the list. The head node of the linked list will be the last node of the linked list and the last one will be the head node.


1 Answers

The general recursive algorithm for this is:

  1. Divide the list in 2 parts - first node and rest of the list.
  2. Recursively call reverse for the rest of the linked list.
  3. Link rest to first.
  4. Fix head pointer

Here is the code with inline comments:

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

I hope this picture will make things clearer:

image
(source: geeksforgeeks.org)
.

like image 109
codaddict Avatar answered Sep 25 '22 20:09

codaddict