## DEV Community is a community of 698,016 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # LinkedList Questions: [Optimal] Find Middle Element Kathan Vakharia
DS-Algo Tenderfoot | Computer Scientist | Aspiring Gopher | DataScience Enthusiast | Python & C++ 💕

In this series of posts, I will discuss coding questions on the `LinkedList` Data structure.
The posts in this series will be organized in the following way,

2. Possible Explanation 📝
3. Documented C++ Code 🧹
4. Time and Space Complexity Analysis ⌛🌌

## The Question

Given a non-empty, singly linked list with head node `head`, return a middle node of the linked list.

If there are two middle nodes, return the second middle node.

💡 Give yourself at least 15-20 mins to figure out the solution :)

## Explanation

I hope you have read the previous article because I want to relate the ideas of both approaches rather than making you feel, an optimal solution is a completely new thing!

👀 Observation: If you recall from the last post, we can reach the middle node after `floor(L/2)` iterations.

Remember the above point, I'll come to this point after we see the algorithm.

Here's the algorithm.

1. Initialize two pointers, `fast` and `slow` both pointing to `head` initially.
2. Move `fast` double the speed than `slow` untill `fast` becomes NULL or it has reached the last node.

``````//pseudo code
while fast!=NULL and fast->next != NULL
fast = fast->next->next
slow = slow->next
``````
3. return `slow` .

### Why does this work?

First of all, we can either have an odd length linkedlist or an even length LinkedList.

• Case 1: Odd length
• `fast` will point to the last node after `floor(L/2)` iterations.
• Case 2: Even Length
• `fast` will become NULL after traversing the entire list in `floor(L/2)` iterations.

So no matter what the type of LinkedList, one of the loop termination conditions will hit after `floor(L/2)` iterations, and by that time `slow` would be pointing to the required middle node. ## C++ Code

``````//Definition for singly-linked list.
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

``````

### Solution

``````  ListNode *middleNode(ListNode *head)
{
ListNode *fast;
ListNode *slow;

//make fast reach the end of the list by moving it double time the slow
while (fast != nullptr && fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}
//* now slow will point to the required node

return slow;
}
``````

## Complexity Analysis

`N`: Length of Linked List.

### Time Complexity: O(N)

We are doing O(N/2) iterations which asymptotically is the same as O(N)

### Space Complexity: O(1)

We didn't use any extra space.