Question

Help in Linked list....

Explain the Function of reversing a link list using recursive function..

Answer 1

A recursive function for reversing a singly linked list would probably just need the current item's address and the pointer (to the next item's) address passed to it. When it gets NULL for an address, that would be the base case. On the unwind, it would just set the pointer to the previous and just keep returning the address of the (originally) end item. The calling routine would need to take the return value and change the root pointer.

All that said, linked lists are usually longer than the kernel will allow recursion depth. In other words, the kernel won't allow as many recursions as there are items in the list. Usually, only about 64 levels are allowed.

Answer 2

This is how I would attempt it. It's pseudo-code.
```
// Base function to start out with
void reverse(list) {
if (list->head != NULL) {
reverse_r(list, list->head);
}
}

// Actual recursive function
void reverse_r(list, node) {
if (node->next != NULL) { // (2)
reverse_r(list, node->next); // (1)
node->next->next = node; // (4)
} else {
list->head->next = NULL; // (5)
list->head = node; // (3)
}
}
```
Initially it will keep going through the recursive call until it gets to the last node. (1)
The last node will have NULL as its next node.
The last node always falls through the if statement so it ends the recursive loop. (2)
The last node gets set as the head of the list. (3)
The second to last node will make the last node's next node point. (4)
This will happen also to the node before the second to last node all the way until the first node.
The first node will have it's next node set to NULL, so in the future we know it is the last node. (5)