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
headinitially say,
* fast=headand
* slow=headMake the pointer
fasttwice as fast as pointerslowby incrementing pointerfastby two positions and pointerslowby one position until pointerfastandfast->nextis not NULL.When the pointer
fastreaches to the end of the linked list, pointerslowwould still be at the middle, thereby pointing to the mid of the linked list.Return the value at pointer
slow.
i.e., returnslow->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.
Top comments (0)