Segmentation fault in a function to reverse a singly linked list recursivley.

Question

I am implementing a function to recursively reverse a linked-list, but getting seg-fault.

typedef struct _node {
   int data;
   struct _node *next;
} Node, *NodeP;

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL;
   if(first->next == NULL) return first;

   NodeP rest = recursiveReverseList(first->next);
   rest->next = first;
   first->next = NULL;

   return first;
}

Can you please help?

P.S. The iterative version is working fine though. Its not homework. Just practicing C.

Thank you all :)

Answer 1

Your algorithm seems to be wrong. You need to return the pointer to the head of the new list, but you are returning the pointer to the last item.

Indeed, you perhaps need both of them: a pointer to the head and the pointer to the last item.

Answer 2

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

You are doing steps 1 and 2 correctly but I guess you've messed up in steps 3 and 4. I would suggest you try this:

NodeP recursiveReverseList(NodeP first){
   if(first == NULL) return NULL; // list does not exist.
   if(first->next == NULL) return first; // list with only one node.

   NodeP rest = recursiveReverseList(first->next); // recursive call on rest.
   //rest->next = first; CHANGE THIS
   first->next->next = first; // make first next to the last node in the reversed rest.

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

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

.

EDIT:

PS: I've not tested this. So try it and let us know :)

I've tested the above function and seems to work as expected. You can try the program here: http://ideone.com/bQXAV

Answer 3

i think

rest->next = first;

should be

first->next->next = first;

Answer 4

@Unicornaddict has already posted a correct algorithm.

But, if you are still getting segmentation fault, I suspect you are making some mistake in calling the function from main.

Correct:

head->next = recursiveReverseList(head->next);

Explanation:

• Pass head->next to the recursive function. If you pass head, it will do something like

Before call:
head ---> A ---> B ---> C
After call:
head <--- A <--- B <--- C

which will make head point to NULL and A point to head

• After passing head->next as argument, state of the list is:

head ---> A <--- B <--- C

So, you need to make head point to rest (C in this case).