How do you reverse a single linked list in recursive method?

Answer 1

Reversing a singly-linked list is (surprisingly) simple and can be done non-recursively. The following function accepts a reference to the current head of the list and returns the new head after reversing the list.

node* reverse (node* head) {

if (!head) return head;

node *lead, *temp;

lead = head;

while (lead->next) {

temp = lead->next;

lead->next = temp->next;

temp->next = head;

head = temp;

}

return head;

}

Doing the same thing recursively is a bit more tricky but it can be done as follows.

node* reverse (node* head, node* prev=NULL) {

node* temp;

if (!head) {

return head;

} else if (!head->next) {

head->next = prev;

return head;

} else {

temp = head->next;

head->next = prev;

return reverse (temp, head);

}

}