47
LinkedList Questions: [Optimal] Find Middle Element
In this series of posts, I will discuss coding questions on the
The posts in this series will be organized in the following way,
LinkedList
Data structure.The posts in this series will be organized in the following way,
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 :)
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.
fast
and slow
both pointing to head
initially.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
return slow
.
First of all, we can either have an odd length linkedlist or an even length LinkedList.
-
fast
will point to the last node afterfloor(L/2)
iterations.
-
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.
//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) {}
};
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;
}
N
: Length of Linked List.We are doing O(N/2) iterations which asymptotically is the same as O(N)
We didn't use any extra space.
47