Linked List: Find middle element in Linked List

Problem Statement:

You are given an single LL.
You need to fing the middle element.

Example

Input : 1->2->3->4->5->6

Output : 4

Solution

The solution is very simple.

We take 2 pointers, Fast and Slow.

Fast will move 2 places at a time.

Slow will move 1 place at a time.

When fast pointer reaches to end of the LL, slow pointer will be pointing to the middle element.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

#include<iostream>
#include<vector>

using namespace std;

struct Node 
{
    int data;
    struct Node* next;
};

void insert_at_begenning ( struct Node **head_pointer, int data)
{
    // allocate memory for new node
    struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));

    // assign the data to new node
    temp_node->data = data;

    // initialize the new node to point to NULL
    temp_node->next = NULL;

    // if this is the first pointer, then this is the head pointer
    if (*head_pointer == NULL)
    {
        *head_pointer = temp_node;
    }
    else
    {
        // point the next of the present pointer to the head pointer
        temp_node->next = *head_pointer;

        //then move the reference of head pointer to the current pointer
        *head_pointer = temp_node;
    }
}

void display_list(struct Node **head_pointer)
{
    // take a reference to head pointer for navigation
    struct Node *temp = *head_pointer;

    while(temp != NULL)
    {
        if(temp->next != NULL)
            printf("%d -> ", temp->data);
        else
            printf("%d", temp->data);

        //navigate to next pointer
        temp = temp->next;
    }
    printf("\n");
}

void middleNode(Node* head) 
{

     Node* slow=head;
     Node* fast =head;

     while(fast!=NULL&& fast->next!=NULL)
     {
         fast = fast->next->next;
         slow = slow->next;
     }
   
    cout<<"The middle node is\n"<<slow->data<<endl;;

 }

   int main()
{
    struct Node *list_1 = NULL; 
    Node *result = NULL;

    insert_at_begenning(&list_1,1);
    insert_at_begenning(&list_1,3);
    insert_at_begenning(&list_1,2);
    insert_at_begenning(&list_1,1);

    printf("Original List\n");
    display_list(&list_1);

    middleNode(list_1);
    

    return 0;
}

Output:

Original List
1 -> 2 -> 3 -> 1
The middle node is
3