How will you find the middle of a Linked List?

Question: Given a Linked List, we need to find the middle of the list and print the number.

Input: 4, 8, 15, 16, 23, 42, 99

Output: 16

This is a very basic question and is a part of a bigger problem. However, there are several approaches to solve the above problem.

BRUTE-FORCE APPROACH

In this approach, we count the number of nodes in the list for each of the node and see whether it is the middle.

struct node * bruteForce(struct node * head)
{
	// making 2 temporary variables
	struct node * temp1 = head;
	struct node * temp2 = head;

	// index for current node
	int index = 1;

	while(temp2 != NULL)
	{
		// to count the number of nodes
		int count = 0;

		// counting nodes for each node
		temp 1 = head;
		while(temp1 != NULL)
		{
			count++;
			temp1 = temp1 -> next;
		}

		// the terminating condition
		if(index == (count/2))
			break;

		index++;
		temp2 = temp2 -> next;
	}
	// the temp2 points to the middle
	return temp2;
}

Time Complexity: O(n²)
Space Complexity: O(1)

MORE SIMPLIFIED APPROACH

In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up-to that node.

struct node * middleInTwoScans(struct node * head)
{
	struct node * temp = head;

	// counting the number of nodes
	int count = 0;
	while(temp != NULL)
	{
		count++;
		temp = temp -> next;
	}

	// to get the middle node count
	count = count/2;

	// returning to first position
	temp = head;

	// traversing for n/2 times
	while(count--)
		temp = temp -> next;

	// temp points at middle node
	return temp;
}

Time Complexity: Time for finding the length + Time for locating middle node = O(n) + O(n) ≈ O(n)
Space Complexity: O(1)

USING HASH TABLE

What we can do is create a hash table and store the index of all the nodes in the List. Then to get the middle node, we can directly point to the node (n/2), where n is the size of the Linked List.

struct node * hashTableMiddle(struct node * head)
{
	struct node * temp = head;

	int count = 0;
	while(temp)
	{
		count++;
		temp = temp -> next;
	}

	// using array to create hash table
	struct node * arr = (struct node *)malloc(sizeof(struct node)*count);

	temp = head;
	count = 0;
	while(temp)
	{
		arr[count] = temp -> data;
		count++;
		temp = temp -> next;
	}

	return arr[(count/2)];
}

Time Complexity: O(n)
Space Complexity: O(n)

USING ONLY ONE SCAN – THE MOST EFFICIENT WAY

We can solve this problem using only one scan on the Linked List. The approach lies in a simple trick of using two pointers to traverse the list.

• ptr1 travels one node at a time
• ptr2 travels two nodes a time.

Thus, when ptr2 reaches the end of the Linked List, ptr1 will point at the middle of the Linked List.

// implementing a function that returns the middle of a Linked List
struct node * findMiddleOfLinkedList(struct node * head)
{
	// a pointer that travels one node a time
	struct node * slowPtr = head;
	
	// a pointer that travels two nodes at a time
	struct node * fastPtr = head;
	
	while(fastPtr -> next != NULL)
	{
		// the slow Ptr moves one step
		slowPtr = slowPtr -> next;
		
		// the fast Ptr moves two steps
		fastPtr = fastPtr -> next;
		if(fastPtr == NULL)
			break;
		
		fastPtr = fastPtr -> next;
		if(fastPtr == NULL)
			break;
	}
	
	// the slow Ptr now points at the middle of the Linked List
	return slowPtr;
}

Time Complexity: O(n)
Space Complexity: O(1)

You can download the working sample of the code here implementing the last method. Open it using any of your favorite editor (gEdit, Notepad++, wordpad etc…)