Introduction

When list length is unknown, you cannot jump directly to the midpoint. This is common with linked lists and stream-like traversals where counting first can be expensive. The standard solution is a two-pointer scan that finds the middle in one pass and constant extra memory.

Why Unknown Size Changes the Approach

For arrays, midpoint is easy because random access is available and length is known. For singly linked lists:

• Length is not known without traversal.
• Random access is not available.
• Extra passes can be costly on long lists.

A two-pass strategy still works:

1. Traverse once to count nodes.
2. Traverse again to index count // 2.

But one-pass logic is usually preferred for performance and simplicity.

Tortoise and Hare Algorithm

Use two pointers:

• slow moves one node per step.
• fast moves two nodes per step.

When fast reaches the end, slow is at the middle.

1class Node:
2    def __init__(self, value, nxt=None):
3        self.value = value
4        self.next = nxt
5
6
7def middle_node(head):
8    if head is None:
9        return None
10
11    slow = head
12    fast = head
13
14    while fast and fast.next:
15        slow = slow.next
16        fast = fast.next.next
17
18    return slow
19
20
21def build(values):
22    head = None
23    for v in reversed(values):
24        head = Node(v, head)
25    return head
26
27
28h = build([10, 20, 30, 40, 50])
29print(middle_node(h).value)  # 30

Complexity:

• Time is linear.
• Extra space is constant.

This is optimal for a single traversal requirement.

Even-Length Lists and Definition Choices

For even length, there are two middle nodes. Different systems choose different conventions:

• Return second middle, which is what the basic loop above returns.
• Return first middle by changing loop condition.

First-middle variant:

1def first_middle_node(head):
2    if head is None:
3        return None
4
5    slow = head
6    fast = head
7
8    while fast.next and fast.next.next:
9        slow = slow.next
10        fast = fast.next.next
11
12    return slow
13
14h2 = build([1, 2, 3, 4, 5, 6])
15print(first_middle_node(h2).value)  # 3

Choose one behavior and document it in the function contract.

Single-Pass Alternative: Moving Midpoint Counter

Another one-pass method increments a midpoint pointer every second step.

1def middle_by_counter(head):
2    mid = head
3    cur = head
4    i = 0
5    while cur:
6        if i % 2 == 1:
7            mid = mid.next
8        cur = cur.next
9        i += 1
10    return mid

It works but is less clear than tortoise and hare and easier to get wrong on boundary cases.

Applying to Streams and Iterators

For true iterators where elements are consumed once and not linked, exact middle in one pass is impossible without storing data because you do not know where the end is in advance. Options:

• Buffer all items then index midpoint.
• Use reservoir-like approximations if exact middle is not required.

Linked list middle works because each node is revisitable through references while traversing.

Testing Strategy

Cover these cases:

• Empty list.
• One element.
• Odd length.
• Even length.
• Very long list for performance confidence.

1def to_list(head):
2    out = []
3    while head:
4        out.append(head.value)
5        head = head.next
6    return out
7
8assert middle_node(build([1])) .value == 1
9assert middle_node(build([1, 2, 3])).value == 2
10assert middle_node(build([1, 2, 3, 4])).value == 3
11assert first_middle_node(build([1, 2, 3, 4])).value == 2
12assert middle_node(None) is None

Tests should explicitly state which middle is expected for even lengths.

Common Pitfalls

• Assuming array logic applies directly to linked lists. Fix by using pointer-based traversal, not indexing.
• Forgetting to handle empty input. Fix by returning None early.
• Not defining behavior for even-length lists. Fix by choosing first-middle or second-middle and documenting it.
• Advancing fast without checking fast.next. Fix by using a safe loop condition.
• Running two passes in performance-critical paths without need. Fix by adopting one-pass two-pointer logic.

Summary

• Unknown-size linked lists are best handled with the two-pointer method.
• Tortoise and hare finds the middle in one pass and constant space.
• Even-length behavior must be defined as part of API contract.
• One-pass alternatives exist, but clarity favors two pointers.
• Strong boundary tests prevent most implementation errors.