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

[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]

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 of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *