write c program to find the middle node of a linked list. This is very basic interview question asked generally from fresher. more experience professional also may face this question.

Use concept of Floyd’s Cycle-Finding Algorithm” also known as “The Tortoise and the Hare Algorithm”
  1. Traverse the linked list using two pointers ( slow pointer and fast pointer).
  2. Move slow pointer by one and fast pointer by two.
  3. When the fast pointer will reach to the end of linked list, the slow pointer would have moved exactly half the linked list , thus slow pointer would point to the middle node of the linked list.

 c program to find the middle node of a linked list

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

typedef struct Link {
	struct Link* next;
	int data;
} list;

list *head = NULL; // head pointer

void addnode(int num);
void printList();
void freememory();

void findMiddle()
{
	if (head == NULL)
	{
		printf("List is empty\n");
		return;
	}
	// slow pointer
	list* slow_ptr = head;
	list* fast_ptr = head;
	while (slow_ptr && fast_ptr && fast_ptr->next)
	{
		slow_ptr = slow_ptr->next;
		fast_ptr = fast_ptr->next->next;
	}
	if (slow_ptr)
	{
		printf("The middle node is %d", slow_ptr->data);
	}
}

int main() {
	addnode(1);
	addnode(2);
	addnode(6);
	addnode(4);
	addnode(5);
	addnode(7);
	addnode(3);
	printList();
	findMiddle();
	freememory();
	return 0;
}

void addnode(int num)
{
	// if node is empty
	if (head == NULL)
	{
		// create first node
		head = (list *) malloc(sizeof(list));
		head->data = num;
		head->next = NULL;
	}
	else
	{
		// if node is not empty,go to last node
		list *tmp = head;
		while (tmp->next)
			tmp = tmp->next;

		// create new node and append to last node
		list *node = (list *) malloc(sizeof(list));
		node->data = num;
		tmp->next = node;
		node->next = NULL;
	}
}

void printList()
{
	list *tmp = head;
	if (tmp == NULL)
		return;

	printf("The list is ");

	while (tmp) {
		printf("%d ", tmp->data);
		tmp = tmp->next;
	}
	printf("\n");
}
void freememory()
{
	list *tmp = head;
	if (tmp == NULL)
		return;
	list *curr;
	while (curr = tmp) {
		tmp = tmp->next;
		free(curr);
	}
}

Ref:

http://www.algo-faq.com/Linked-List/Find-the-middle-node-of-a-linked-list.php




Related Contents to follow