Reversing a linked list recursively

Question

This appears to work. Are there any edge cases I am missing? What are your thoughts on the algorithm and implementation?

template <typename el>
void Linkedlist<el>::reverse() {
 Node<el> * oldHead = head;
 Node<el> * tailAfterReversal = recReverseList( head->getNextNode() );
 oldHead->setNextNode(NULL);
 tailAfterReversal->setNextNode(oldHead);
}
// Reverses part of a linked list starting from toRevesrPortionHead, returns the tail node
// after the reversal operation has been performed
template <typename el>
Node<el> * Linkedlist<el>::recReverseList( Node<el> * toReversePortionHead ) {
 if ( toReversePortionHead->getNextNode() == NULL ) {
 head = toReversePortionHead;
 return toReversePortionHead;
 }
 Node<el> * tailAfterReversal = recReverseList( toReversePortionHead->getNextNode() );
 tailAfterReversal->setNextNode(toReversePortionHead);
 toReversePortionHead->setNextNode(NULL);
 return toReversePortionHead;
}

Answer 1

Algorithm

1. Since its recursive and O(n), for large n you may get a stack overflow.

2. It will fail if the head is null (empty).

3. This part is redundant:

   toReversePortionHead->setNextNode(NULL);

Since in each stack call you change the next pointer of the next to the current. For example:

In the base case :

(4) -> (5) -> (9) -> (10) -> nil

First pop:

(4) -> (5) -> (9) <- -> (10)

Second pop:

(4) -> (5) <- -> (9) <- (10)

You will end up with:

(4) <- -> (5) <- (9) <- (10)

So you set the member next of the resulting node to null

nil <- (4) <- (5) <- (9) <- (10)

---

Node

Your node is generic, you should make it a nested class. Also your get and set methods are too verbose and I would personally omit them.

---

NULL:

If you are using C++11 you should be using nullptr. If you are curious why is a better alternative you could check out this link https://stackoverflow.com/questions/13816385/what-are-the-advantages-of-using-nullptr

---

Code :

I would change it to this:

template <typename el>
void Linkedlist<el>::reverse() {
 if(!empty())
 recReverseList(head)-> next = nullptr;
}
template <typename el>
Node * Linkedlist<el>::recReverseList( Node* node ) {
 if ( node->next == nullptr ) 
 return head = node; 
 return recReverseList( node->next )->next = node;
}

• Nash Vail: Thank you so much for all the inputs, very very insightful. TIL a new C++ shorthand!