Recursion: Given a linked list, find the middle element recursively

Problem Statement:

You are given a LL, you need to find the middle element recursively.

Example:

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

Solution Explanation:

We will solve the problem with help of fast and slow pointer and when the first pointer reaches the end, slow pointer will be pointing to the mid of the LL.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;


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

Node* getMid(Node* slow, Node* fast)
{
    if(fast==NULL||fast->next==NULL)
    {
        return slow;
    }

    return getMid(slow->next,fast->next->next);
}

Node* middleNode(Node* head) 
{
    return getMid(head,head);
}

void insertNode(struct Node** head, int data)
{
   struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
   new_node->data = data;
   new_node->next = (*head);
   (*head) = new_node;
}

int main(){
   struct Node* head = NULL;
   insertNode(&head, 1);
   insertNode(&head, 2);
   insertNode(&head, 3);
   insertNode(&head, 4);
   insertNode(&head, 5);
   insertNode(&head, 6);
   insertNode(&head, 7);
   Node* result = middleNode(head);
   cout << result->data << endl;
   return 0;
}

Output

4