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
[code lang=”c”]
#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);
}
[/code]