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

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

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
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

// 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);

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
{
// 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)