How do you recursively reverse a singly linked list using c plus plus?

Answer 1

In this case recursion is not necessary, an iterative process is more efficient.

Start by pointing at the head node. While this node has a next node, detach its next node and insert that node at the head. Repeat until the original head node has no next node. At that point the head has become the tail and all the nodes are completely reversed.

The following example shows how this can be implemented, where the list object contains a head node (which may be NULL), and each node has a next node. The tail node's next node is always NULL.

void reverse(list& lst)

{

if( node* p=lst.head )

{

while(p->next)

{

node* n=p.next; // point to the next node

p.next=n.next; // detach the next node

n.next=lst.head; // insert the detached node at the head

lst.head=n; // set the new head node

}

}

}