Middle of the Linked List
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the middle node of a linked list (the second middle if there are two).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1You could count the nodes first, then walk half. Can you do it in one pass?
- Hint 2Two walkers, one twice as fast as the other.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two friends walk along a road. One walks twice as fast. When the fast friend reaches the end of the road, the slow friend has covered exactly half the distance, so he is standing in the middle. You never had to measure the road.
- The obvious way
Count the nodes, then walk n/2 steps: two passes.
- The key insight
Move a slow marker one step and a fast marker two steps at a time. When the fast marker cannot go further, the slow marker is at the middle (the second middle for even lengths).
- The algorithm
- Slow and fast both start at the head.
- While fast and the node after it exist: slow moves 1 step, fast moves 2.
- Return slow.
Watch it run
Examplelist = 1 -> 2 -> 3 -> 4 -> 5
Both at 1.
slow 1, fast 1
Where people slip
- For an even number of nodes this returns the SECOND middle, which is what the problem wants.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.