C program to find the middle element of a linked list.

In this post, we are going to write a C program to find the middle element of a linked list.
There are many ways of doing this. One way is to find the length of the linked list in one traversal and then traverse the linked list to half of the length calculated.

Another better approach is to use two pointers and traverse the linked list with one pointer traversing at two times the speed of another pointer. Hence when the faster pointer will reach at the end, Slower one will be at the midpoint of the linked list.

Another method is to traverse the linked list and use a single pointer moving with half the speed of traversing, so when the traversing will complete the pointer will be at the midpoint of the linked list.

Time Complexity of all the above methods is O(n).

// THis program calculates the number of occurrences of an element in the linked list
#include<stdlib.h>
#include<stdio.h>

// Creating a structure for linked list node
struct node
{
	int data; // variable to store data in node
	struct node *next; //pointer to store the address of the connected node
};

// This function will add a node at the end of the linked list
// This functions takes pointer to pointer of head and value to be appended into 
// the linked list
void append(struct node **head_ref, int value)
{
	// Creating a memory block using malloc to store the data and assigning 
	// it to a struct node pointer named temp
	struct node *temp = (struct node *)malloc(sizeof(struct node)) ;

	// assigning the data to the node
	temp->data = value;

	// assigning the next pointer to NULL, as 
	// it will be the last node of linked list
	temp->next = NULL;

	// if head is NULL, then we will just point the head node to
	// the temp node created above and return
	if(*head_ref == NULL) 
	{
		*head_ref = temp;
		return;
	}

	// creating a struct node pointer called trav to traverse the list
	// to the end
	struct node *trav = *head_ref;

	// traversing the list to the end
	while(trav->next != NULL)
		trav = trav->next;

	// pointing the next pointer of last node to the temp node 
	trav->next = temp;
}


// This function prints the linked list and takes the head pointer as 
// its parameter
void print_list(struct node *head)
{	
	// traversing the linked list till the end and printing 
	// the data in the nodes
	while(head != NULL)
	{
		printf("%d ", head->data);
		head = head->next;
	}

	// printing new line after printing the whole linked list
	printf("\n");
}

// This function returns the middle element of the linked list
// this function uses two pointer, one traverse two times faster than other
// hence when the faster pointer reaches the end, slower one is in the middle
int middle_element(struct node *head)
{
	// declaring and initialising two pointers to traverse the linked list
	struct node *fast_ptr = head ;
	struct node *ptr = head;

	// traversing the linked list 
	while(fast_ptr != NULL && fast_ptr->next != NULL)
	{
		fast_ptr = (fast_ptr->next)->next;
		ptr = ptr->next;
	}

	// returning middle element
	return ptr->data;
}

// This function returns middle element using only one pointer
// In this function, the pointer traverse with half the speed,
// so when the list is traverse using head pointer, the middle pointer
// reaches the mid point of the list.
int middle_elem(struct node *head)
{
	// declaring and initializing the middle pointer 
	struct node *middle = head;

	// declaring and initializing a count variable to zero
	int count = 0;

	// traversing the linked list and updating the middle pointer 
	// only when the count is odd
	while(head != NULL)
	{
		// if count is odd update middle pointer
		if(count %2)
			middle = middle->next;
		
		// increament count
		++count;

		// updating head pointer to traverse the linked list
		head = head->next;
	}

	// returning the middle element
	return middle->data;
}


// Main driver function
int main()
{
	// this is to read input and write output in 
	// input.txt and output.txt files in the same folder
	#ifndef LOCAL_TEST
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	// creating head node of the linked list and assigning it to NULL
	struct node *head = NULL;

	// call the append function to add elements to the list
	append(&head, 7);
	append(&head, 8);
	append(&head, 15);
	append(&head, 12);
	append(&head, 9);

	printf("Printing all the elements : ");

	// printing the list with all elements
	print_list(head);

	// printing middle element using two pointer method
	printf("Middle element is : %d \n", middle_element(head));

	// printing middle element using single pointer method
	printf("Middle element is : %d \n", middle_elem(head));


	return 0;
}

Expected output:

Printing all the elements : 7 8 15 12 9 
Middle element is : 15 
Middle element is : 15 

Time complexity : O(n)

Show CommentsClose Comments

Leave a comment