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.

C Code To Compare Two Linked Lists

Compare Two Linked Lists:

Here we are comparing two linked lists which have same type of data. If number of nodes and the data held by each node are equal then two linked lists are equal.

C Code To Compare Two Linked Lists:

#define EQUAL 0
#define NOT_EQUAL 1

int comp ( struct node *p, struct node *q )
{
if( !p && !q )
return EQUAL;

if(  ( !p && q )  ||  ( !q && p ) )
return NOT_EQUAL;

return (  ( p->data == q->data )  &&  ( comp ( p->node, q->node ) )  );
}

On invoking this recursive function, it will return 0 ( equal ) or 1 ( not equal ) based on linked lists passed to it.