Floyd's Hare and Tortoise Algorithm

1. Overview:

In this tutorial, we're going to explain how to find the middle element of a linked list in C++ using Floyd's hare and tortoise algorithm.

How does this work?

We will traverse linked list using two pointers. Moving one pointer by one and the other pointers by two. When the fast pointer reaches the end slow pointer will reach the middle of the linked list. For eg. Suppose we have a linked list of 5 nodes and we want to find the middle element. We start both the slow and fast pointer from the head node. In step two, slow pointer reaches the second node but fast one is at node 3. In second step, slow pointer reaches to node three but fast pointer is at the end i.e position 5. Now the value of fast pointer gets NULL so the while loop breaks and the middle element is the data at slow pointer. When you get the middle element just return and print it.

Code:

//Find Middle Element of Linked List using Hare and Tortoise Algorithm
#include <bits/stdc++.h>
using namespace std;

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

void findMiddleElement(Node *node)
{
    Node *fast = node;
    Node *slow = node;

    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    cout << "Middle Element: " << slow->data;
}

int main()
{
    Node *head = new Node();
    head->data = 18;

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

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

    Node *third = new Node();
    third->data = 40;

    Node *fourth = new Node();
    fourth->data = 18;

    head->next = first;
    first->next = second;
    second->next = third;
    third->next = fourth;

    findMiddleElement(head);

    return 0;
}

This is how you find the middle element of a linked list using Hare and tortoise algorithm.