Skip to content

Instantly share code, notes, and snippets.

@radiantly
Last active March 23, 2021 20:16
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save radiantly/c70bd5a3d16c2d6a6d8de0d2ef55783c to your computer and use it in GitHub Desktop.
Save radiantly/c70bd5a3d16c2d6a6d8de0d2ef55783c to your computer and use it in GitHub Desktop.
Reversing a linked list (stack) consisting of only unique pointers
#include<iostream>
#include<memory>
#include<functional>
struct Node {
int val;
std::unique_ptr<Node> next;
Node(int value) : val{value} {}
};
class Stack {
std::unique_ptr<Node> top;
public:
void push(int);
std::optional<int> pop();
void display();
void reverse();
};
void Stack::push(int value) {
auto tmp = std::make_unique<Node>(value);
tmp->next = std::move(top);
top = std::move(tmp);
}
std::optional<int> Stack::pop() {
if (!top) return {};
auto tmp = std::move(top);
top = std::move(tmp->next);
return tmp->val;
}
void Stack::display() {
for (auto ptr = std::cref(top); ptr.get(); ptr = std::cref(ptr.get()->next))
std::cout << ptr.get()->val << " ";
std::cout << std::endl;
}
void Stack::reverse() {
std::unique_ptr<Node> pointTo;
while (top) {
auto nextNode = std::move(top->next);
top->next = std::move(pointTo);
pointTo = std::move(top);
top = std::move(nextNode);
}
top = std::move(pointTo);
}
int main() {
Stack s;
s.pop();
s.reverse();
s.display();
s.push(1);
s.push(2);
s.display();
s.push(3);
s.push(4);
s.display();
s.pop();
s.push(5);
s.push(8);
s.display();
s.reverse();
s.display();
s.pop();
s.pop();
s.display();
s.push(2);
s.push(1);
s.push(1);
s.push(0);
s.display();
return 0;
}
/*
2 1
4 3 2 1
8 5 3 2 1
1 2 3 5 8
3 5 8
0 1 1 2 3 5 8
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment