Finding the middle element of a linked list

Published on Oct 4, 2021

Subscribe to our newsletter and never miss any upcoming articles

In this article we are going to find the middle element of a singly linked list. For example, if the given linked list is 1->2->3->4->5 then the output should be 3. If there are even nodes, there will be two middle nodes, hence the second middle element must be printed. For instance, if the linked list is 1->2->3->4->5->6, the output should be 4.

There are two methods to solve this problem

1. Traverse the whole linked list and count the number of nodes. Then traverse the list again till you reach the half length i.e0 'count/2' and return the node at 'count/2'

2. Floyd's Hare and Tortoise algorithm: Here we use two pointers to traverse the linked list. One moves faster than the other and when the fast pointer reaches the end, sloe pointer will reach the middle of the linked list.

For this article we will use the naïve approach i.e method one. We'll cover Floyd's algorithm in another article.

• Code:
#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node *next;
Node()
{
this->next = NULL;
}
};

void findMiddle(Node *node)
{
Node *temp = node;

int count=0;
while(node!=NULL)
{
count++;
node = node->next;
}
int mid=count/2;

while(mid--)
{
temp=temp->next;
}
cout<<"Middle Element: "<<temp->data<<endl;
}

int main()
{

Node *first = new Node();
first->data = 20;

Node *last = new Node();
last->data = 30;

first->next = last;