C Program to find Middle element in a linked list

Approach #1:

The Naïve way to do this, is to loop through the linked list and increment a count variable with every iteration till null is encountered. Then finally traverse again from the start to count/2.

Isn’t this the obvious approach…..

Let’s go to the not so obvious one…

 Approach#2:

Maintain two pointers from the start of the linked list. A fast and a slow pointer. Increment slow pointer by one and the fast pointer by two. When the fast one reaches the end , the slow one wil reach the middle node of the linked list.

Let’s try to code it:

Program:

#include<stdio.h> /*for printf & scanf*/

#include<stdlib.h> /*for malloc*/

struct node

{

    int data;

    struct node* next;

};

void insert(struct node** head_ref,int data)

{

    struct node* temp=(struct node*)malloc(sizeof(struct node));

    temp->data=data;

    temp->next=(*head_ref);

    (*head_ref)=temp;

}

void findMid(struct node* head)

{

    struct node* slow_ptr=head;

    struct node* fast_ptr=head;

    if (head!=NULL)

    {

        while(slow_ptr&&fast_ptr&&fast_ptr->next)

    {

        slow_ptr=slow_ptr->next;

        fast_ptr=fast_ptr->next->next;

    }

    }

    printf("\n\nThe Middle point of the given linked list is %d\n",slow_ptr->data);

}

void printList(struct node* head)

{

    struct node*temp=head;

    while(temp)

    {

       printf("%d -> ",temp->data);

       temp=temp->next;

    }

    printf("NULL");

}

int main()

{

    struct node* head=NULL;

    int i;

    for(i=1;i<=5;i++)

        insert(&head,i);

    printf("\nLinked List : \n\n");

    printList(head);

    findMid(head);

    return 0;

}

Viva La Raza

Sid