DSA Middle of the Linked List

The problem

A linked list is a chain of nodes. Each node holds a value. Each node also holds a link to the next node.

The problem gives the head of the chain. The head is the first node. The answer is the middle node of the chain.

An odd-length list has one middle node. An even-length list has two middle nodes. This problem asks for the second of the two.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


cases = [
    ([1, 2, 3, 4, 5], 3),
    ([1, 2, 3, 4], 3),
    ([1, 2], 2),
    ([7], 7),
]
for values, expected in cases:
    print(render(build(values)), "| middle:", expected)

Read one row at a time. Five nodes have the single middle 3. Four nodes have middles 2 and 3, and the answer is 3. Two nodes answer 2 for the same reason.

Intuition

The first idea uses a plain Python list. Copy every value into the list. Then read the value at index len // 2.

A list supports direct index access. A linked list does not. The copy buys that access with extra memory.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


head = build([1, 2, 3, 4, 5])
values = []
node = head
while node is not None:
    values.append(node.value)
    node = node.next
print("copied values:", values)
print("index:", len(values) // 2)
print("middle value:", values[len(values) // 2])

The copy works. It also stores every value a second time. The chain itself already holds those values in order.

A leaner first idea counts the nodes instead. Counting needs no copy. It still walks the chain once just to learn its length.

Brute force

The brute force counts the nodes first. It then walks half that count from the head. The node it lands on is the middle.

Two walks are the cost. The first walk only measures. The second walk does the finding.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def middle_brute(head):
    count = 0
    node = head
    while node is not None:
        count += 1
        node = node.next
    steps = count
    node = head
    for _ in range(count // 2):
        node = node.next
        steps += 1
    return node, steps

cases = [[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2], [7]]
for values in cases:
    node, steps = middle_brute(build(values))
    print(values, "middle:", node.value, "node visits:", steps)

The visit count shows the bill. Five nodes cost seven visits. The count visits five nodes, and the walk then moves two more times.

The method is correct on every case. It is also wasteful. One walk should be enough if the length never needs to be known.

The optimal solution: slow and fast pointers

Move two pointers at two speeds, so the slow pointer sits halfway when the fast pointer finishes. That one sentence is the whole method.

The slow pointer moves one node per round. The fast pointer moves two nodes per round. Both pointers start at the head.

The loop runs while the fast pointer can still move twice. Each round moves slow once and fast twice. The fast pointer covers the chain at double speed, so slow covers exactly half.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def middle_node(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

cases = [[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2], [7]]
for values in cases:
    node = middle_node(build(values))
    print(values, "middle:", node.value)

All four cases from the start of the article pass. The even case answers 3. The fast pointer steps past the last node there, and slow rests on the second middle.

No count is stored. No copy is built. The chain is walked once.

Walkthrough

Watch the two pointers on the list 1 to 5. The printout shows both values after each round.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


head = build([1, 2, 3, 4, 5])
slow = head
fast = head
print("start: slow", slow.value, "fast", fast.value)
step = 0
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    step += 1
    fast_text = fast.value if fast is not None else None
    print("round", step, ": slow", slow.value, "fast", fast_text)
print("middle:", slow.value)

Round one puts slow on 2 and fast on 3. Round two puts slow on 3 and fast on 5.

The loop then stops. The fast pointer sits on the last node, and its next link is None. Slow rests on 3, the middle node.

Complexity

The time cost is O(n) for a chain of n nodes. The fast pointer makes one pass, and the slow pointer moves inside the same pass.

The space cost is O(1). Two pointers are stored, and nothing grows with the chain.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def brute_steps(head):
    count = 0
    node = head
    while node is not None:
        count += 1
        node = node.next
    return count + count // 2

def fast_slow_rounds(head):
    slow = head
    fast = head
    rounds = 0
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        rounds += 1
    return rounds

for size in [5, 10, 20, 40]:
    values = list(range(1, size + 1))
    head = build(values)
    print("nodes", size, "brute visits:", brute_steps(head), "fast-slow rounds:", fast_slow_rounds(head))

The counts grow in a straight line. Doubling the nodes doubles the brute visits. It also doubles the fast-slow rounds.

The saving is a constant factor, not a new growth rate. One pass replaces a pass and a half. The copy version also drops its extra list.

Edge cases and pitfalls

An empty list has no middle node. The function returns None there. The loop test handles that case before any move happens.

The loop test needs both checks. It tests fast itself and then fast.next. Dropping the second check makes the code read next on the last node twice removed, and an even-length walk can fail.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def middle_node(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

empty = middle_node(None)
print("empty:", empty)
print("single:", middle_node(build([7])).value)
print("two nodes:", middle_node(build([8, 9])).value)
print("six nodes:", middle_node(build([1, 2, 3, 4, 5, 6])).value)

Two nodes answer the second node. Six nodes answer 4, the second of middles 3 and 4. The even-length rule stays consistent at every size.