Tuesday, 21 February 2017

C Program To Find The Middle Element of The Linked List

This Question has been appeared in the interview of following companies:

Payu, Samsung, MAQ software, Microsoft, Nagarro, Netskope, Adobe, Amazon, Flipkart, GE, IgniteWorld

Source: geeksforgeeks

In the exact question you have given a linked in which you have to find the middle element of the Linked List. For example if the Linked List is 1->2->5->7->9 then the middle element is 5. 

In the case of even node, their will be two elements in the middle one and you have to return the second middle element of the Linked List. For example if the Linked List is 1->3->4->5->6->8 then the middle element is 5. 

In the exact question you don't have to write the complete program, you just have to complete a methode which will accept only one argument (i.e head of the Linked List) and you have to return the middle element. There are several test cases and this method is individually called for each test case. In the case of empty Linked List you have to return -1.

The function which you have to complete is given below.
 


struct Node {
    int data;
    Node* next;
}; */

/* Should return data of middle node. If linked list is empty, then  -1*/
int getMiddle(Node *head)
{
     /* write your code here */

}


ALGORITHM

1.  set count:=0
2.  set current:=head #pointer contains memory address of head node of the Linked list
3.  while current!=NULL
4.        set  count:=count+1
5.        set  current=current->next
6.  EndWhile
7.  set n=count/2
8.  if head=NULL
9.        return -1
10. Else
11.       set count2=0
12.       set current:=head
13.       while current!=NULL
14.              if count2=n
15.                     return current->data
16.              else
17.                     set count2=count2+1
18.                     set current=current->next
19.              End IfElse
20.       EndWhile
21. Exit


The completed function is

/* Link list Node 
struct Node {
    int data;
    Node* next;
}; */

/* Should return data of middle node. If linked list is empty, then  -1*/
int getMiddle(Node *head)
{
     struct Node *current;
     int count=0;
     current=head;
     if(head==NULL)
     {
          return -1;
     }
     else
     {
         current=head;
         while(current!=NULL)
         {
               count++;
               current=current->next;
         }
         int n=count/2;
         int count2=0;
         current=head;
         while(current!=NULL)
         {
              if(count2==n)
              {
                  return current->data;
              }
              else
              {
                  count2++;
                  current=current->next;
              }
         }
     }

}


I have also coded complete program incase you want to write this program from beginning.

#include <stdio.h>
#include <stdlib.h>
struct node{
  int data;
  struct node *next;
}*root=NULL,*temp;
void insert(int item);
int middle_Element(struct node *head);
void print();
int main()
{
    
    int choice,item;
    do
    {
      printf("\nEnter the element you want to insert in the Linked List: ");
             scanf("%d",&item);
             insert(item);
             printf("\nDo you want to coninue[1/0]: ");
             scanf("%d",&choice);
    }while(choice==1);
    printf("\n\nThe original Linked List is:\n");
    print();
    printf("\nMiddle element of the Linked List is: %d",middle_Element(root));
    return 0;
}
void insert(int item)
{
    if(temp==NULL)
    {
         temp=(struct node*)malloc(sizeof(struct node));
         temp->data=item;
         temp->next=NULL;
         root=temp;
    }
    else
    {
         temp->next=(struct node*)malloc(sizeof(struct node));
         temp=temp->next;
         temp->data=item;
         temp->next=NULL;
    }
}
void print()
{
    struct node *current;
    current=root;
    while(current!=NULL)
    {
         printf("%d->",current->data);
         current=current->next;
    }

}
int middle_Element(struct node *head)
{
  struct node *current;
     int count=0;
     current=head;
     if(head==NULL)
     {
          return -1;
     }
     else
     {
         current=head;
         while(current!=NULL)
         {
               count++;
               current=current->next;
         }
         int n=count/2;
         int count2=0;
         current=head;
         while(current!=NULL)
         {
              if(count2==n)
              {
                  return current->data;
              }
              else
              {
                  count2++;
                  current=current->next;
              }
         }
     }
}


OUTPUT:

 


EmoticonEmoticon