Given the head of a linked list, return the middle node. If there are two middle nodes, return the second one.
DSA Animator › DSA Revision › Linked List › Middle of Linked List
Remember: when fast finishes, slow is halfway. This also finds the split point for palindrome and reorder problems. The video solves Middle of Linked List (LeetCode 876, Easy) with the Fast & Slow Pointers pattern from the Linked List topic, and you can replay every step in the interactive Middle of Linked List animation.
Given the head of a linked list, return the middle node. If there are two middle nodes, return the second one.
For 1, 2, 3, 4, 5, the middle is 3. For 1 to 6, there are two middles, 3 and 4, so return 4.
Counting the length first and then walking half of it takes two passes. One pass is enough with two speeds.
Move slow by one and fast by two. When fast reaches the end, slow has covered half the distance. So slow is at the middle.
Both start at 1. Slow moves to 2, and fast to 3. Slow moves to 3, and fast to 5, the last node. Fast cannot move further, so the middle is 3.
In code, loop while fast and fast dot next are not null. Move slow once and fast twice. Return slow, so it's O of n time and O of 1 space.
Remember: when fast finishes, slow is halfway. This also finds the split point for palindrome and reorder problems.