Removing Characters from a String

found an interesting learning resource http://www.bogotobogo.com/ it also has a section on programming questions, not so extensive as the awesome http://geeksforgeeks.org/, but has some good problems to solve, with solutions. here is my solution to the "Removing Characters from a String" problem (http://www.bogotobogo.com/cplusplus/quiz_strings_arrays.php). it is not better, just a different approach

#include 
#include 

int main()
{
  std::string name("Ludwig Van Beethoven");
  std::string remove("aeiouAEIOU");
  int walk = 0;
  int last = 1;
  while (last < name.length() && walk < name.length()) {
      auto found = remove.find(name[walk], 0);
      if (found != std::string::npos) {
          char ch = name[walk];
          name[walk] = name[last];
          name[last] = ch;
          ++last;
      } else {
          ++walk;
      }
  }
  std::cout << "Hello, " << name.substr(0, walk+1) << "!\n";
}

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