Finding the Middle Node

There are two standard approaches and they differ in what they trade.

The first counts the nodes in one pass, then walks half of that distance in a second pass. It is easy to follow and needs only one pointer, but it touches every node twice.

The second uses two pointers moving at different speeds. The fast pointer moves two nodes per step and the slow pointer one. When the fast pointer reaches the end, the slow pointer is exactly at the middle. It touches each node about half as many times and uses no extra memory beyond the second pointer, but the loop condition is subtler because you have to check that the fast pointer and its successor both exist.

The mechanism behind the fast and slow version is that the fast pointer is always one full lap of the slow pointer ahead. When the list has an odd number of nodes, the fast pointer reaches the last node and the slow pointer sits on the true middle. When the list has an even number, the fast pointer goes one past the end and the slow pointer sits on the second of the two central nodes, which is the usual convention.

The trade-off to name is that the two pointer version is one pass instead of two, which matters for a list that might be long enough that the second pass is expensive, for example one backed by a disk read rather than memory. It also avoids the case where the list changes between the two passes, which would leave the second pass working on stale information.

Move the fast pointer two nodes at a time and the slow pointer one. Stop when the fast pointer cannot move two more steps, and the slow pointer is at the middle.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def middle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


print(middle(build([1, 2, 3, 4, 5])).value)
print(middle(build([1, 2, 3, 4])).value)
print(middle(build([1])).value)

The outputs are 3, 3 and 1. For the five element list the middle is the third node. For the four element list the answer is the third node as well, which is the second of the two central ones. The single element list is its own middle.

The mechanism is the relative speed. The fast pointer covers two nodes for every one the slow pointer covers, so when the fast pointer has walked the whole list the slow pointer has walked exactly half of it, and the slow pointer is standing on the middle node.

The trade-off to name is the loop condition. It tests the fast pointer and its successor, because advancing the fast pointer by two needs both to exist. If you only test the fast pointer, a list of even length will make the fast pointer step off the end and the function will raise an error on the last iteration. The two pointer version is also the one to reuse for cycle detection, where the same speed difference makes the pointers meet instead of separating.

Count the nodes in a first pass, then walk half of that count from the head in a second pass.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def middle_by_count(head):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    current = head
    for _ in range(length // 2):
        current = current.next
    return current


print(middle_by_count(build([1, 2, 3, 4, 5])).value)
print(middle_by_count(build([1, 2, 3, 4])).value)

The outputs are 3 and 3. For the five element list the length is five and the integer division gives two steps, landing on the third node. For the four element list the length is four and two steps lands on the third node as well, which is the second of the two central nodes and matches the convention used by the two pointer version.

The mechanism is that the count tells you how many half steps to take. Using integer division on the length means an odd length lands on the true middle and an even length lands on the later of the two central nodes, so the two approaches agree on every input.

The trade-off to name is the second pass. The counting version reads every node twice, so it is about twice the work of the two pointer version in terms of memory traffic, and it is not safe if the list can change between the passes. In exchange it is simpler, uses one pointer instead of two, and does not have the off-by-one risk in the loop condition that the fast pointer version carries. For a linked list held in memory both are fine, and the choice is really about readability.