1
\$\begingroup\$

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;

}
\$\endgroup\$
2
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you so much for all the inputs, very very insightful. TIL a new C++ shorthand! \$\endgroup\$ – Nash Vail Oct 10 '15 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.