Given the head of a singly linked list, return its middle node. If the list has an even number of nodes there are two middle nodes; return the second one. The judge prints the list starting from the node you return.
- The list has 1 to 100 nodes
- 1 <= Node.val <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The two pass approach counts the length n, then walks n / 2 steps from the head. It is O(n) and fine, but interviewers want the slow and fast pointer version: fast moves twice as quickly, so when fast has covered the whole list, slow has covered half of it. Using the condition fast != null && fast.next != null makes slow stop at the second middle for even lengths.
Algorithm
- Set
slow = headandfast = head. - While
fastandfast.nextare not null, moveslowone step andfasttwo steps. - Return
slow.
O(n)Space: O(1)fast.next != null && fast.next.next != null. Know both variants.class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next # 1 step fast = fast.next.next # 2 steps return slow # second middle for even lengths