Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
[1, 100].1 <= Node.val <= 100This technique uses two pointers, 'slow' and 'fast'. Both start at the head of the list. The 'slow' pointer progresses one node at a time while the 'fast' pointer moves two nodes at a time. When the 'fast' pointer reaches the end of the list, the 'slow' pointer will be at the middle node. This works because the 'fast' pointer traverses the list twice as fast as the 'slow' pointer, thus splitting the path lengthwise in half.
In C, we define a simple singly linked list structure and implement the two-pointer approach to find the middle node. The 'slow' pointer advances one step while the 'fast' pointer advances two steps, and once 'fast' reaches the end, 'slow' will be pointing at the middle node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the list, because we are iterating through the list once.
Space Complexity: O(1), since we are using a constant amount of space.
This approach involves two passes over the list. The first pass calculates the total number of nodes. In the second pass, we traverse halfway through the list to reach the middle node by stopping at n/2, where n is the number of nodes. This explicitly determines the node that marks the middle of the list.
This C implementation counts the nodes in a linked list using an initial loop, then follows a second traversal that stops at the mid-point to return the middle node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for two full passes through the list.
Space Complexity: O(1) as only a few extra variables are used.
| Approach | Complexity |
|---|---|
| Two-pointer Technique (Slow and Fast) | Time Complexity: O(n), where n is the number of nodes in the list, because we are iterating through the list once. |
| List Length Calculation | Time Complexity: O(n) for two full passes through the list. |
L13. Find the middle element of the LinkedList | Multiple Approaches • take U forward • 104,476 views views
Watch 9 more video solutions →Practice Middle of the Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor