Road To Code

Road To Code

Floyd's Hare and Tortoise Algorithm

Yash Naravade's photo
Yash Naravade

Published on Oct 4, 2021

2 min read

Subscribe to our newsletter and never miss any upcoming articles

Listen to this article

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.

Linked list cycle.png

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.

 
Share this