How to use the two pointers trick in a linked list

A very simple trick which has multiple uses: finding the middle of a linked list, finding a certain node from the end (e.g. the 3rd node from the end back) or finding if a linked list has loops. I'll just post the code here, using the same structure as in the previous post. It has comments and it's really simple.

Finding the middle of a linked list:

   1:  int findMiddle(node* head) {

   2:      node* middle = head; // the middle will be here

   3:      while (head != 0 && head->next != 0) {

   4:          head = head->next->next; // advance the head by two positions forward

   5:          middle = middle->next; // advance the middle by only one position

   6:      }

   7:      return middle->data;

   8:  }

The solution is O(n) because the algorithm has to go through all the nodes once.

Finding if a linked list has loops (uses almost the same code):

   1:  bool hasLoops(node* head) {

   2:      node* slowPtr = head; //we'll move slower into the list using this pointer

   3:      while (head != 0 && head->next != 0) {

   4:          head = head->next->next; // advance the head by two positions forward

   5:          slowPtr = slowPtr->next; // advance the slowPtr by only one position

   6:          if (head == slowPtr) //these can never become equal unless one pointer loops

   7:              return true;     //back to a previous position, which means there's a loop

   8:      }

   9:      return false;

  10:  }

Again, the solution is O(n) in the worst case because the algorithm has to go through (potentially) all the nodes - it depends on where the loop is.

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:  }