Home Linked List How will you find the middle of a Linked List?

How will you find the middle of a Linked List?

by nikoo28
0 comment

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(n2)
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…)

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More