Thursday, June 20, 2013

Finding the middle of the linked list

Given a single linked list, how do you find the middle of the list?

One simple method is to traverse through the list twice once to find it's length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance of improving this method. 

In this method we traverse the list only once. We take two pointers, one, a slow pointer which will advance one node at a time; and a fast pointer which will advance two nodes at a time. we iterate through the list until the fast pointer reaches the end of the list. At this stage, the slow pointer would be pointing to the middle of the linked list.

Following is the C++ function which implements this method. For working program please visit this post.




 SLLNode* getMiddle()
 {
  //if the list is empty or has a single node; return head
  if( head == NULL || head->getNext() == NULL )
   return head;
   
  SLLNode *slow = head;
  SLLNode *fast = head->getNext();
   
  while( fast != NULL )
  {    
   //move fast pointer two steps ahead
   if( fast->getNext() != NULL )
   {
    fast = fast->getNext()->getNext();
   }
   else
    break;
   //move slow pointer one step 
   slow = slow->getNext();
  }
  return slow;
 }