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,
 Question Link ❓
 Possible Explanation 📝
 Documented C++ Code 🧹
 Time and Space Complexity Analysis ⌛🌌
The Question
Given a nonempty, 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.
https://leetcode.com/problems/middleofthelinkedlist/
💡 Give yourself at least 1520 mins to figure out the solution :)
Explanation
LinkedList Questions: Middle Element of Linked List  Naive Approach
Kathan Vakharia ・ Jul 11 ・ 2 min read
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.
 Initialize two pointers,
fast
andslow
both pointing tohead
initially. 
Move
fast
double the speed thanslow
untillfast
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
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 afterfloor(L/2)
iterations.

 Case 2: Even Length

fast
will become NULL after traversing the entire list infloor(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 of Linked List
//Definition for singlylinked 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;
fast = slow = head;
//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.
Discussion (0)