O(n) O(1)
Intuition
Advance a slow pointer one step and a fast pointer two steps. When fast reaches the end, slow sits at the middle.
Explanation
Tortoise and hare
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Because fast moves twice as fast, it reaches the end just as slow reaches the midpoint. For an even count, this naturally lands on the second middle node.
Worked example
[1,2,3,4,5] → slow ends at 3; return [3,4,5].
Complexity
- Time: O(n).
- Space: O(1).
Implementation
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}