Interview Question
Given a linked list, find its middle element.
Solution
A brute force technique is to count the number of elements in the linked list by traversing the linked list once and incrementing a counter flag, then traversing the list again till the middle value. Another approach, that is actually sought after in interviews is to maintain two pointers - one slow and one fast, to traverse the list. The slow pointer traverses the list normally, one element at a time, while the fast pointer jumps an element each time. When the fast pointer reaches the end of the list, the slow pointer points to the middle element.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data ;
struct node * next ;
} * head = NULL ;
void push ( int val )
{
struct node * newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
newnode -> next = NULL ;
struct node * ptr = head ;
if ( ptr == NULL )
head = newnode ;
else
{
while ( ptr -> next )
ptr = ptr -> next ;
ptr -> next = newnode ;
}
}
void print ()
{
struct node * itr ;
itr = head ;
while ( itr )
{
printf ( " %d " , itr -> data ) ;
itr = itr -> next ;
}
}
int middle ()
{
struct node * slow , * fast ;
slow = head ;
fast = head ;
if ( head )
{
while ( slow -> next && fast -> next )
{
slow = slow -> next ;
fast = fast -> next -> next ;
}
}
return slow -> data ;
}
int main ()
{
push ( 2 ) ;
push ( 3 ) ;
push ( 1 ) ;
push ( 8 ) ;
push ( 7 ) ;
print () ;
printf ( " The middle element is %d " , middle () ) ;
printf ( " \n ") ;
print () ;
return 0 ;
}
