C Program To Find Middle Element Of Linked List

C Program To Find Middle Element Of Linked List:

Finding middle element of linked list is frequently asked question about in interviews. There are two simple ways of finding the middle element of a linked list.

Method #1 To Find Middle Element Of Linked List:

Put a counter [ count = 0; ] in traverse and increase the counter [ count++; ]whenever you pass a node.

This gives total number of elements in the given linked list.

Now divide counter by 2 [ count /= 2; ].

Again traverse linked list, decreasing the counter [ count--; ] until it becomes zero [ count == 0; ].

Here is another solution which  is more elegant, compact and efficient.

Method #2 C Code To Find Middle Element Of Linked List:

In this method, we will have to pointers say p and q.

p is incremented once [ p = p->next; ].

q is double incremented [ q = q->next->next; ].

So, when q reaches last element of linked list, p is pointing to the middle element.

void middle ( mynode *head )
{
mynode *p = head;
mynode *q = head;

if( q != NULL )
{
while(  (p->next)!= NULL  &&  (q->next->next) != NULL  )
{
p = ( p != ( mynode * ) NULL  ?  p->next  :  ( mynode * ) NULL );
q = ( q! = ( mynode * ) NULL  ?  q->next  :  ( mynode * ) NULL );
q = ( q != ( mynode * ) NULL  ?  q->next  :  ( mynode * ) NULL );
}
printf(" The middle element is [%d] \n", p->value );
}
}

This function prints middle element of given linked list.