Return the middle node of a singly linked list in one pass (for even length, the second of the two middles).
Use the slow/fast (tortoise and hare) pointers: advance slow by one and fast by two each step; when fast reaches the end, slow is at the middle. O(n) time, O(1) space, one pass — no need to count length first.
static class Node { int val; Node next; Node(int v){ val = v; } }
public static Node middle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}class Node { constructor(v) { this.val = v; this.next = null; } }
function middle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}class Node:
def __init__(self, val):
self.val = val
self.next = None
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowThe two-speed pointer technique underlies cycle detection, palindrome checks on lists, and splitting a list for merge sort.
Why is the slow/fast approach preferred over counting the length and walking to n/2?