For problems 56 assume that the linked lists are formed with

For problems 5-6, assume that the linked lists are formed with nodes of the following type: struct Node int data Node *next The nodes are not part of a class and you should not assume that any functions already exist that you can use.

Solution

int getMedian(Node * head)
{
   int count=0, mid, median=0;
   Node * t= head;
   if(t!= NULL)
   {
       count++;
       while(t->next !=NULL)
       {
           count++;
           t=t->next;
       }
      
      
   }
   mid = count/2;
   t=head;
   if(count % 2 == 0)
   {
       for(int i=1; i<mid; i++)
       {
           t=t->next;
       }
       median=(t->data + t->next->data)/2;
   }
   else
   {
       for(int i=1; i<=mid; i++)
       {
           t=t->next;
       }
       median=t->data;
   }
   return median;
}