remove duplicates from an unsorted linked list

more fun with algorithms: how to remove duplicates from an unsorted linked list in cpp?
easy - just walk along the list and delete duplicate items.
but how to know an item is a duplicate?
well, for every item we could scan the list from the beginning, but this is a ridiculously naive solution - how about keeping all values we encounter while iterating and checking if we have already met a current value?
putting those in an unordered set would be good enough i'd say

#include 
#include 
using namespace std;

struct List {
 int data = 0;
 List* next = nullptr;
 List(int x) : data(x) {}
};

void remove_duplicates(List* head) {
 std::unordered_set cache;
 cache.insert(head->data);
 List* next = head->next;
 while (next != nullptr) {
  if (cache.count(next->data) > 0) {
   head->next = next->next;
   delete next;
   next = head->next;
  } else {
   cache.insert(next->data);
   head = next;
   next = head->next;
  }
 }
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; ++index) {
  List* next = new List(index);
  //a silly way to make duplicates in the list
  if (next->data % 2 == 0) {
   next->data = 2;
  } else if (next->data % 3 == 0) {
   next->data = 3;
  }
  list->next = next;
  list = next;
 }
 
 remove_duplicates(head);
 
 while (head != nullptr) {
  printf("%d\n", head->data);
  head = head->next;
 }
 
 return 0;
}

https://ideone.com/K19v5o

reverse linked list

been fooling around writing solutions to algorithms in c++.
here is a solution to reverse a linked list. nothing new - the idea is to revert the links, but before that keep somewhere the links to the nodes to come so that this information is not lost during iterating.
shouldn't have any bugs due to corner cases, i hope :D

#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
 List* next = head->next;
 head->next = nullptr;
 while (next != nullptr) {
  List* movingHead = next->next;
  next->next = head;
  head = next;
  next = movingHead;
 }
 return head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}

https://ideone.com/Wj9ocK

it seems like often it is easier to come up with a recursive solution. here is one: recursively go the the end of the list and then, on winding back, attach "prior" nodes as "next"s to the new head

#include 
using namespace std;

struct List {
 int value = 0;
 List* next = nullptr;
 List(int x) : value(x) {}
};

List* reverse(List* head) {
  List* list = head;
  List* new_head = list;
  if (list->next != nullptr) {
     list = reverse(list->next);
     new_head = list;
     while (list->next != nullptr) {
      list = list->next;
     }
     list->next = head;
     head->next = nullptr;
  }
  return new_head;
}

int main() {
 List* head = new List(1);
 List* list = head;
 for (int index = 2; index < 10; index++) {
  List* next = new List(index);
  list->next = next;
  list = next;
 }
 head = reverse(head);
 
 while (head != nullptr) {
  printf("%d\n", head->value);
  head = head->next;
 }
 return 0;
}

https://ideone.com/Lcfc4r