(list)+recursive reverse algorithm for singly linked lists

Pretty simple, returns the last node as that's the new root node.
Uses default parameters to make sure the first node has next set to null.

1 files changed, 15 insertions, 0 deletions

diff --git a/list.cpp b/list.cpp
index 593a87e..5dc6d18 100644
--- a/list.cpp
+++ b/list.cpp
@@ -42,6 +42,18 @@ List<T> *append(List<T> *lst, T value)
   return lst;
 }
 
+/** Reverse a list
+ */
+template <typename T>
+List<T> *reverse(List<T> *lst, List<T> *prev = NULL)
+{
+  auto next = lst->next;
+  lst->next = prev;
+  if (next == NULL)
+    return lst;
+  return reverse(next, lst);
+}
+
 template <typename T>
 std::ostream& operator<<(std::ostream& ostream, const List<T> *lst)
 {
@@ -57,5 +69,8 @@ int main(void)
   for (int i = 2; i < 10; ++i)
     lst = append(lst, i);
   std::cout << lst << std::endl;
+  lst = reverse(lst);
+  std::cout << lst << std::endl;
+  delete lst;
   return 0;
 }