Implement an algorithm to reverse a singly linked list (with and without recursion).

Below is a sample implementation that reverses a singly linked list using recursion.
The simplest way to do this with recursion is:
void rev(Node* head, Node* prev)
{
if (!head) return;
rev(head->next, head);
head->next = prev;
}
Head is now pointing to the end instead of the start of the list. To fix that, you can use a wrapper
function like below:
void reverse(Node* &p)
{
if (!p) return;
for (Node* tmp = p; tmp->next; tmp = tmp->next) { }
rev(p, NULL);
p = tmp;
}
An iterative algorithm to reverse a singly linked list is presented below:
struct node *revlist (struct node *root)
{
struct node *np = root, *t, *r = 0;
while (np) {
root = np;
t = np->next;
np->next = r;
r = np;
np = t;
}
return root;
}
Note that an iterative solution to this problem is better than a recursive one, since every recursive
call uses up more memory on the stack, and large lists can cause the stack to overflow. The iterative
solution uses a constant amount of memory, so it’ll work fine no matter how big the list is. It is also
faster, because it avoids all of the recursive function calling overhead. In general, iterative solutions
are usually better in practice than recursive solutions.