# Linked List reversal

Recursive version. The only interesting function:

        List& List::reverse()
{
if (empty())
{   return *this;
}
int val = head();
//
// The fun bit.
// See if you can figure this bit out.
return pop().reverse().append(val);
}


The rest:

#include <iostream>
#include <memory>
struct List
{
struct Node
{
int     val;
std::unique_ptr<Node>   next;
Node(){}
Node(int v, Node* oldTail)
: val(v)
, next(nullptr)
{
oldTail->next.reset(this);
}
friend std::ostream& operator<<(std::ostream& s, Node const& data)
{
return s << data.val << " ";
}
};
Node    sentinal;
Node*   tail;
public:
List()
: tail(&sentinal)
{}
bool empty() const
{
return &sentinal == tail;
}
{
// Pre-Condition not empty
return sentinal.next->val;
}
List& append(int val)
{
tail = new Node(val, tail);
return *this;
}
List& pop()
{
// Pre-Condition not empty
sentinal.next.reset(sentinal.next->next.release());
tail = sentinal.next.get() ? tail : &sentinal;
return *this;
}
List& reverse();
friend std::ostream& operator<<(std::ostream& s, List const& data)
{
for(Node* loop = data.sentinal.next.get(); loop != nullptr; loop=loop->next.get())
{   s << *loop;
}
return s << "\n";
}

};


See if you can figure this bit out.

Is this meant to be a Programming Puzzle?

You don't call append until after you finish calling reverse; reverse is recursive; so all the append calls will be called after all the reverse calls: and that explains why reverse will eventually terminate i.e. why the list will eventually be empty.

From a code-review point of view:

1. I fear that a recursive implementation might exceed your finite maximum stack size if the list is long.
2. You're deleting and creating new Node objects; you might instead be able to do it in a way that reuses existing Node instances.

Also, it should be spelled "sentinel".

• Fixed everything but recursion. Because thats the bit that makes it "fun". Apr 3 '14 at 16:00
• Not a puzzle. Valid code needs checking. Just fun code. Now the next time somebody posts a singly linked list implementation I have a reference to point them to. :-) Apr 3 '14 at 16:01
• @LokiAstari: "Now the next time somebody posts a singly linked list implementation" Given the popularity of these implementations on this site, I hope you can keep up. ;-)
– Jamal
Apr 3 '14 at 19:56
• @LokiAstari: Also, it appears that you've made some changes based on this answer (at least pertaining to the spelling). Please reverse those individual changes as per site policy.
– Jamal
Apr 3 '14 at 20:04

Some minor things:

• You could just leave out public since you're only dealing with structs. You could still maintain the following indentation to really keep it separate from the Node code.

• In C++11, you can now use default constructors if you still need your own:

Node() = default;

• Consider making List a templated class if you'd like it to handle other types of values.