Problems
Middle of the LinkedList
Easy·Tagslinked-listtwo-pointers
Problem Statement
Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList.
If the total number of nodes is even, return the second middle node.
Examples
Example 1
Input
head: [1, 2, 3, 4, 5]Linked list
Output
"3"Why
The list has an odd number of nodes (5). The middle node has the value 3.
Example 2
Input
head: [1, 2, 3, 4, 5, 6]Linked list
Output
"4"Why
The list has an even number of nodes (6). The two middle nodes are 3 and 4. We return the second middle node, which has the value 4.
Example 3
Input
head: [1]Linked list
Output
"1"Why
The list has only one node, which is the middle node itself.
Constraints
- •1 <= Number of Nodes <= 10000
- •1 <= Node.val <= 100000
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
A brute-force approach would be to traverse the linked list to find its total length, then traverse it again to reach the middle (length / 2). Can we do it in a single pass?
Hint 2
Use the Fast and Slow pointers method. Move the 'fast' pointer two steps at a time, and the 'slow' pointer one step at a time.
Hint 3
When the 'fast' pointer reaches the very end of the list, where do you think the 'slow' pointer will be?