How to reverse a linked list

The intent of this blog is to provide short or long solutions to the most common puzzles or algorithmic problems which could be asked at interviews, etc. I'm mainly writing this for myself, in C++, to help me in the future, but who knows... maybe someone else will find it useful too.

I'm going to start with something really basic, which is the problem of reversing a simple linked list. I'll only add here the most important functions, building the rest of the solution is just not worth the reading space. For this post, and the rest, I will assume a simple linked list has the following structure:

   1:  struct node {

   2:      int data; //let's keep it simple, assume it's a list of integers

   3:      node* next; //pointer to the next node in the list

   4:  };

There are two ways to do it, and both are pretty simple: iteratively and recursive. The interative solution looks something like this:

   1:  node* reverse_interative(node* head)

   2:  {

   3:      if (head == 0 || head->next == 0)

   4:          return head; //just return if the list is empty or has only one item

   5:      node* prev = 0;

   6:      node* next = 0;

   7:      while (head->next != 0) { //we go forward through the list

   8:          next = head->next; // remember the next item at each step

   9:          head->next = prev; // modify the pointer to the next item, to point at the previous item

  10:          prev = head; // at the next step we move forward, so prev is also moved forward

  11:          head = next; //  go to the next element

  12:      }

  13:      head->next = prev; // we stopped because (head->next == 0), so it's the last element which must become the head

  14:      return head;

  15:  }

Recursively, it's even simpler:

   1:  node* reverse_recursive(node* head, node* prev) // start with prev = 0, for the first call

   2:  {

   3:      if (head == 0) // if we're at the end, return the previous item, which is the end of the original list

   4:          return prev;

   5:      node* next = head->next; //keep the next item in a temp node

   6:      head->next = prev; // modify the pointer to the next item, to point at the previous item

   7:      return reverse_recursive(next, head); // do the same for the next item

   8:  }