How do you find the middle node of a linked list in one pass?
Use two pointers: slow moves one step, fast moves two. When fast reaches the end, slow is at the middle. For an even length it lands on the second of the two middle nodes.
Explain it simply
Two friends walk along a platform. One walks at normal speed, the other at double speed. When the fast one reaches the end of the platform, the slow one has covered exactly half the distance, so they are standing at the middle.
You never need to count the length first, which would cost a second pass.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromArray(arr) {
const dummy = new ListNode(0);
let tail = dummy;
for (const v of arr) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
function toArray(head) {
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function middle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
console.log(middle(fromArray([1, 2, 3, 4, 5])).val); // Output: 3
console.log(middle(fromArray([1, 2, 3, 4])).val); // Output: 3Complexity
Time O(n), space O(1).
What to say in the interview
"I use slow and fast pointers, moving fast two steps for each one of slow. When fast cannot move further, slow is at the middle. It is a single pass, O(n) time and O(1) space, and I mention that for even lengths this version returns the second middle node."
Common mistakes
- Writing the loop condition as only fast.next, which crashes on even-length lists when fast becomes null.
- Counting nodes first and then walking again, which is correct but needs two passes.