Reverse a queue

Preamble
Reverse a singularly linked list using recursion.

Solution
Its trivial code, but nice now by passing the pointer to head_->_next to ReverseInternal() stores this pointer in the parameter of the call.

Code:
[js]
Node* ReverseInternal(Node *head_)
{
if (head_->_next == nullptr)
{
return head_;
}

Node* newHead = ReverseInternal(head_->_next);
head_->_next->_next = head_;

return newHead;
}

Node* Reverse(Node *head_)
{
if (head_ != nullptr)
{
Node* newHead = ReverseInternal(head_);
head_->_next = nullptr;
return newHead;
}
else
{
return head_;
}
}
[/js]

Full solution

Code:
[js]
#include
using namespace std;

class Node
{
public:
Node(string data_, Node* next_) : _data(data_), _next(next_) {}
string _data;
Node* _next;
};

[js]
Node* ReverseInternal(Node *head_)
{
if (head_->_next == nullptr)
{
return head_;
}

Node* newHead = ReverseInternal(head_->_next);
head_->_next->_next = head_;

return newHead;
}

Node* Reverse(Node *head_)
{
if (head_ != nullptr)
{
Node* newHead = ReverseInternal(head_);
head_->_next = nullptr;
return newHead;
}
else
{
return head_;
}
}

void printList(Node* list_)
{
Node* node = list_;
while(node != nullptr)
{
cout << node->_data << " "; node = node->_next;
}

cout << endl; } int main() { unique_ptr D = make_unique(“D”, nullptr);
unique_ptr C = make_unique(“C”, D.get());
unique_ptr B = make_unique(“B”, C.get());
unique_ptr A = make_unique(“A”, B.get());

printList(A.get());

Node* list = Reverse(A.get());

printList(list);

return 0;
}
[/js]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.