Linked lists · routine

The middle node

Write middle(head) returning the value of the middle node of a non-empty list; with an even number of nodes, the second of the two middle ones.

Walk two pointers: one a node at a time, one two at a time. When the fast one runs out, the slow one is in the middle.

right answers
arguments left as they should be
without len, list

Already written for you — you can use these

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5 
6def build(values):
7    head = None
8    for v in reversed(values):
9        head = Node(v, head)
10    return head

def middle(head):
    return head.value

Run adds print(middle(build([1, 2, 3, 4, 5]))) after your code, to try it.

Stuck on the idea rather than the code? The Fast and slow, and a dummy head lesson walks through it.