Question :- C program to find the middle node of a linked list

The simple approach to reach up to middle node we have to know how many nodes are there in linked list and then traverse up to half of that node count. But this solution is not efficient.

Algorithm

/* Function to find the middle of the linked list */
void findMiddle(node *head)
{
    node *slow_ptr = head;
    node *fast_ptr = head;
    if (head!=NULL)
    {
        while (fast_ptr != NULL && fast_ptr->link != NULL)
        {
            fast_ptr = fast_ptr->link->link;
            slow_ptr = slow_ptr->link;
        }
        printf(" The middle element is %d \n", slow_ptr->data);
    }
}

 

But there is another way which is very efficient. Traverse linked list using two pointers named as fast and slow. Move slow pointer by one node and fast pointer by two node in single iteration. When the fast pointer reaches end slow pointer will reach middle of the linked list.

C program to find the middle node of a linked list

#include<iostream>
#include<stdlib.h>

using namespace std;
 
/* List Structure */ 
typedef struct Node
{
	int data;
	struct Node *link;
}node;
 
node *head = NULL;	// Head node to keep track of linked list
 
/* Driver functions */
void findMiddle(node *head);
void insert(int data, int position);
void print();
 
/* Main method */
int main()
{
	insert(0,1);	// Insert Element at first position LINKED-LIST =  / 0 /
	insert(1,2);	// Insert Element at second position LINKED-LIST = / 0 1 /
	insert(2,3);	// Insert Element at third position LINKED-LIST =  / 0 1 2 /
	insert(3,4);	// Insert Element at fourth position LINKED-LIST = / 0 1 2 3/
	insert(4,5);	// Insert Element at fourth position LINKED-LIST = / 0 1 2 3 4/

	print();		// Printing Elements of Linked List
	
	findMiddle(head);	// Find middle element

	return 0;
}
 
/* Function to find the middle of the linked list */
void findMiddle(node *head)
{
    node *slow_ptr = head;
    node *fast_ptr = head;
 
    if (head!=NULL)
    {
        while (fast_ptr != NULL && fast_ptr->link != NULL)
        {
            fast_ptr = fast_ptr->link->link;
            slow_ptr = slow_ptr->link;
        }
        printf(" The middle element is %d \n", slow_ptr->data);
    }
} 
 
/* Function for Inserting nodes at defined position */
void insert(int data, int position)
{
	/* Declaring node */
	node *temp = (node*)malloc(sizeof(node));
	temp->data = data;
	temp->link = NULL;
	
	/* if node insertion at first point */
	if(position==1)
	{
		temp->link = head;
		head = temp;
		return ;
	}
	
	/* Adding & Adjusting node links*/
	node *traverse = head;
	for(int i=0; i<position-2; i++)
	{
		traverse = traverse->link;
	}	
	temp->link = traverse->link;
	traverse->link = temp;	
}
 
/* Function for Printing Linked List */
void print()
{
	printf("\n Linked List = ");
	node *p = head;
	while(p)
	{
		printf(" %d",p->data);
		p = p->link;
	}
	printf(" \n\n");
}

 

Output

Suggested Reading

1. Write a program to reverse a linked list using stack in c++
2. Write a c program to implement a queue using array and linked list
3. Write a c program to implement a stack using an array and linked list