Middle of the Linked List
Problem
Given the head of a singly linked list, return the middle node. If there are two middles, return the second.
head = [1,2,3,4,5]3def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowfunction middleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}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;
}
}ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}Explanation
The classic trick here is the two-pointer "tortoise and hare": run two pointers through the list where one moves twice as fast as the other. When the fast one reaches the end, the slow one is sitting exactly at the middle.
We start slow and fast both at head. Each loop step moves slow by one node and fast by two. The loop continues while fast and fast.next still exist, which is how we safely take that double step.
It works because of the 2-to-1 speed ratio: by the time fast has covered the whole list, slow has covered exactly half of it. For an even-length list this naturally lands on the second middle, which is what the problem wants.
Example: [1,2,3,4,5]. Start both at 1. Step 1: slow→2, fast→3. Step 2: slow→3, fast→5. Now fast.next is null, so we stop and return slow, which is 3.
This makes a single pass and uses just two pointers, so it is both fast and memory-light compared to counting the length first and walking again.