Finding the middle element of a linked list

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 *head = new Node();
    head->data = 18;

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

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


    head->next = first;
    first->next = last;


    findMiddle(head);

    return 0;
}

As you can see from in the code, we made three nodes namely, 'head', 'first' and 'last'. then we traversed from the first to the last node to get the count of total number of nodes. Then we divided count by 2 to get the middle node element and then return it.