Skip to content

Instantly share code, notes, and snippets.

@lelandjansen
Last active August 7, 2016 05:11
Show Gist options
  • Save lelandjansen/2b38abbc1a85ae8085fcf7612338a4fb to your computer and use it in GitHub Desktop.
Save lelandjansen/2b38abbc1a85ae8085fcf7612338a4fb to your computer and use it in GitHub Desktop.
Reverse a singly-linked list
#include <iostream>
#include <vector>
struct Node {
char value;
Node *next;
};
class LinkedList {
public:
LinkedList();
void InsertHead(char value);
void Reverse();
void Print();
~LinkedList();
private:
Node *head;
void Reverse(Node *previous, Node *current);
};
LinkedList::LinkedList() {
head = nullptr;
}
void LinkedList::InsertHead(char value) {
Node *n = new Node;
n->value = value;
n->next = head;
head = n;
}
void LinkedList::Reverse(Node *previous, Node *current) {
if (current->next) Reverse(current, current->next);
else head = current;
current->next = previous;
}
void LinkedList::Reverse() {
Node *n = head;
if (!n) return;
Reverse(nullptr, n);
}
void LinkedList::Print() {
Node *n = head;
while (n) {
std::cout << n->value;
if (n->next) std::cout << " -> ";
n = n->next;
}
std::cout << std::endl;
}
LinkedList::~LinkedList() {
Node *n, *temp;
n = head;
while (n) {
temp = n;
n = n->next;
delete temp;
}
}
int main() {
std::vector<char> values {'d', 'c', 'b', 'a'};
LinkedList ll;
for (char v : values) ll.InsertHead(v);
std::cout << "original: ";
ll.Print();
ll.Reverse();
std::cout << "reversed: ";
ll.Print();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment