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 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.
https://leetcode.com/problems/middle-of-the-linked-list/
💡 Give yourself at least 15-20 mins to figure out the solution :)
Explanation
LinkedList Questions: Middle Element of Linked List - Naive Approach
Kathan Vakharia ・ Jul 11 '21 ・ 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 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;
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.
Top comments (0)