easy
Middle of the Linked List
Return the middle node of a singly linked list. If the list has an even number of nodes, return the second of the two middle nodes.
Constraints
- 1 ≤ number of nodes ≤ 100
Examples
in: head = 1 → 2 → 3 → 4 → 5
out: node 3
in: head = 1 → 2 → 3 → 4 → 5 → 6
out: node 4
Recognition clues
- Singly linked, length unknown
- Want a position at half the length in one pass
- A pointer moving twice as fast finishes when the slow one is halfway
Pattern
Fast & Slow PointersTwo pointers moving at different speeds along a sequence of next links meet if and only if the sequence loops (Floyd). The same trick locates the middle in one pass and finds the cycle entry, all in O(1) space. Any function f: [1..n] -> [1..n] iterated from a start is an implicit linked list.
Solution
Start slow and fast at the head. Move slow one node and fast two nodes per iteration while fast and fast.next are non-null. When fast falls off the end, slow has covered half the distance and sits on the middle node; with an even length this lands on the second middle, matching the requirement.
time O(n)space O(1)
Alternative approaches
- Counting the length then walking
n / 2steps takes two passes and is equally valid.
Code it yourself
Solve in
Hints: