How to find middle element in link list in C program? This is one of the frequently asked interview question specially for less than two years of experience programmer including freshers. Let suppose we have a link list 5 6 7 8 9 , write a c program to print its middle element.

How to find middle element in link list in C programSolution:

Use two pointers to traverse link list, one as “fast” and  second as “slow”.  The fast pointer will increment by two and slower will increment by one. When the list will end the slow pointer will be at the middle.

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

// data structre for link list
typedef struct Node {
	int data;
	struct Node *next;
} list;

list *head = NULL;

// function to insert data in link list
void insertData(int a);
// A function to print a linked list
void DisplayList(list * ptr);
int FindMiddleElement(list * ptr);

int main() {
	//******************************//
	/* Let us create a list */
	/* 5 6 7 8 9 */
	//******************************//
	insertData(5);
	insertData(6);
	insertData(7);
	insertData(8);
	insertData(9);

	// print list
	printf("The list is \n");
	DisplayList(head);

	int element = 0;
	// call FindMiddleElement
	element = FindMiddleElement(head);
	printf("The Middle element is %d \n", element);

	return 0;
}

void insertData(int a) {
	// create first node
	if (head == NULL) {
		head = (list *) malloc(sizeof(list));
		head->data = a;
		head->next = NULL;
	} else {
		// go to last node
		list *p = head;

		while (p->next != NULL)
			p = p->next;
		// create new node
		list *new_one = (list *) malloc(sizeof(list));
		new_one->data = a;
		p->next = new_one;
		new_one->next = NULL;
	}
}

// A function to print a linked list
void DisplayList(list * ptr) {
	while (ptr != NULL) {
		printf("%d ", ptr->data);
		ptr = ptr->next;
	}
	printf("\n");
}

int FindMiddleElement(list * ptr) {
	// slow pointer
	list *slow = ptr;
	// fast pointer
	list *fast = ptr;

	while (fast != NULL && fast->next != NULL) {
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow->data;
}

 

Output:
The list is

5 6 7 8 9 
The Middle element is 7


Related Contents to follow