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); }