Middle Number of Linked List.

Given a non-empty singly linked list, let us find the middle number.

If there are even nodes in the linked list, then there would be two middle nodes so out of two we need to print the second node number.

Example - 1
Input : Linked list : 1 2 3 4 5
output : Middle number : 3

Example - 2
Input : Linked list : 6 7 8 9 2 1
output : Middle number : 9

Steps :

• Create two pointers of type struct node and point both pointers to head initially say,
  * fast = head and
  * slow = head

• Make the pointer fast twice as fast as pointer slow by incrementing pointer fast by two positions and pointer slow by one position until pointer fast and fast->next is not NULL.

• When the pointer fast reaches to the end of the linked list, pointer slow would still be at the middle, thereby pointing to the mid of the linked list.

• Return the value at pointer slow.
  i.e., return slow->data.

C program that finds the middle number of the given linked list.

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

struct node
{
    int data;
    struct node * next;
};  

void displayLL(struct node * head)
{
    int num = 0;
    struct node * temp;
    temp = head;
    temp=head;
    while(temp!=0)
    {
       printf("%d ",temp->data);
       temp = temp->next;
       num++;
    }
} 

void middleNode(struct node *head) 
{ 
    struct node *slow = head; 
    struct node *fast = head; 

    if (head!=NULL) 
    { 
        while (fast != NULL && fast->next != NULL) 
        { 
            fast = fast->next->next; 
            slow = slow->next; 
        } 
    }
    printf("\nMiddle number : %d", slow->data);
} 

int main()
{
   struct node *head = 0, *newnode, *temp; 
   int n, choice, newdata;

// Create Linked List //

   printf("Enter the number of nodes in the list : ");
   scanf("%d", &n);
   for(int i = 1; i<=n; i++)
   {
   newnode = (struct node *)malloc(sizeof(struct node));
   printf("Enter the data%d : ", i);
   scanf("%d", &newnode->data);
   newnode->next = 0;
   if(head == 0)
    {
        head = temp = newnode;
    } 
    else
       { 
        temp->next = newnode;
        temp = newnode;
       }
 }
   printf("--------------------------------\n");
   printf("Linked list : ");
   displayLL(head);
   middleNode(head);
}

I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.