Find the middle element in linked list | Microsoft

Find the middle element in linked list | Microsoft

Question

Write a program to find the middle element in linked list. Given a singly linked list, like 1->2->3->4->5 then output should be 3.

This is one of the important interview questions. Asked in companies such as Amazon, Flipkart, Microsoft, Samsung, Adobe, Vmware etc. 

 

Prerequisite: Pointer to Pointer

Logic

  • Get the numbers from the user and create a list using the append function. In that new elements are added at end of the list.
  • Now Pass the head pointer to the FindMiddle function.
  • Traverse the whole list to find the count of nodes.
  • Reset the pointer and traverse count/2 nodes from the start and print the data.

Program

#include<stdio.h>
struct Node
{
    int data;
    struct Node* next;
};
void FindMiddle(struct Node** head)
{
    int count=0,i;
    struct Node* t= (struct Node*)malloc(sizeof(struct Node));
    /*storing the first element address in t*/
    t=*head;
    /*loop to find the total nodes count*/
    while(t !=NULL)
    {
        count++;
        t=t->next;
    }
    t=*head;                //reset t so it points to head again
    
    /*loop to traverse till the middle*/
    for(i=0;i<count/2;i++)
    {
         t=t->next;
    }
    printf("%d",t->data);   //middle element data    

}
void append(struct Node** Head,int data)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next=NULL;
    struct Node* t = *Head;
    if(*Head == NULL)       //First element in the list (or) head is null
    {
        *Head = temp;
        return;
    }
    /*travese till end*/
    while(t->next!=NULL)
        t= t->next;

    t->next = temp;         //attach new node to the end
}
int main()
{
    int n,data,i;
    struct Node* head = NULL;
    printf("enter n:");
    scanf("%d",&n);
    printf("enter n elements:");

    for( i=0;i<n;i++)
    {
        scanf("%d",&data);
        append(&head,data);
    }
    /*Passing the head pointer to function*/
    FindMiddle(&head);
}

You might also like…

Insert a node at a specific position in LinkedList

To find nth to last element of a Singly LinkedList

Sree Hari Sanjeev

The founder and CEO of Wisdom Overflow. His enthusiasm and effort has taken the blog to next level. You will be motivated just by taking a look at his daily schedule.

Leave a Reply

Your email address will not be published.

4 × 2 =