Find the middle node of the list by using doubly linked list:

Write a program to find the middle node in the doubly linked list. For linked list there is no data limit. And we don’t have any idea to identify how many data are present in the list like array. Here we are going to explain how to find the middle node by using doubly linked list.

We strongly recommend you to try this program by yourself. Before scrolling down your mouse.

Step to find the middle node in linked list:

Step 1: First we need to increment the head node twice

step 2: By the same time we need to increment another temp node once. Note both temp and head node pointing same head node before processing.

step 3: keep on increment till head node reaches NULL or head node’s next node reaches NULL.

step 4: if head node is null then the list contains odd number so we have middle node in that temp node. Or else if the head->next is NULL then the list is even number. It may not have middle element.

 

/* Write a program to find the Middle Node in the given single linked list */ 

#include <stdio.h>
#include <stdlib.h>

struct Node_t
{
   int val;
   Node_t *next;
   Node_t *prev;
};

void push(struct Node_t **head,int data)
{
   struct Node_t *temp;
   temp = (struct Node_t *) malloc(sizeof(struct Node_t));
   temp->val = data;
   temp->next = *head;
   (*head) = temp;
   printf("%d Successfully inserted\n",data);

}
void pop(struct Node_t **head)
{
   if(*head != NULL)
   {
      struct Node_t *temp = *head;
      *head = (*head)->next;
      free(temp);
      printf("Last Node has been deleted\n");
   }
   else
   {
      printf("No Data Found!!\n");
   }

}
void display(struct Node_t *head)
{
   if(head != NULL)
   {
      printf("Nodes Are :\n");
      while(head != NULL)
      {
         printf("%d ",head->val);
         head = head->next;
      }
      printf("\n");
   }
   else
   {
      printf("No Data Found!!!\n");
   }
}
void middlenode(struct Node_t *head)
{
   struct Node_t *midNode = head;
   //struct Node_t *DoubleMoveNode;
   while(head != NULL && head->next !=NULL)
   {
      head = head->next->next;
      midNode = midNode->next;
   }
   if(head != NULL)
   {
      printf("Middle Node is : %d\n",midNode->val);
   }
   else
   {
      printf("Middle Node may be %d . Because the Linked list contain even count\n",midNode->val);
   }
   
}
int main()
{
   int opt,data;
   struct Node_t *head = NULL;
   do 
   {
      printf("1.Push \n2.Pop \n3.Display \n4.Middle Node \n5.Exit \nEnter your Option : ");
      scanf("%d",&opt);
      switch(opt)
      {
         case 1:
            printf("Enter a value : \n");
            scanf("%d",&data);
            push(&head,data);
            break;
         case 2:
            pop(&head);
            break;
         case 3:
            display(head);
            break;
         case 4:
            middlenode(head);
            break;
         case 5:
            printf("User Selected Exit Option\n");
            break;
         default:
            printf("Invalid Option\n");
      }
   }
   while(opt != 5);
   return 0;
}