Return the middle node of a singly linked list. If there are two middle nodes, return the second one.
Problem
Given the head of a singly linked list, return the node that appears in the middle of the list.
If the list has an even number of nodes, there are two middle nodes. In that case, return the second middle node.
The answer should be the node itself, not just its value.
Goal
Find the middle of the list efficiently, ideally in one pass.
Input Format
- A singly linked list is given by its head node.
- Each node contains an integer value and a reference to the next node.
Output Format
- Return the middle node of the linked list.
- If the length is even, return the second of the two middle nodes.
Constraints
- The linked list contains at least 1 node.
- Node values may be any valid integers.
- Try to use extra space.
Example 1
Input
head = [1,2,3,4,5]
Output
[3,4,5]
Explanation
The list has 5 nodes, so the middle node is 3.
Example 2
Input
head = [1,2,3,4,5,6]
Output
[4,5,6]
Explanation
The list has 6 nodes, so there are two middle nodes: 3 and 4. Return the second one, which is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.