Linked List Random Node - Implementation

Here is the full solution:

function getRandom(head)
    result := head.val
    current := head
    i := 1
    while current is not null
        // Select current with probability 1/i
        if random(1, i) = 1 then
            result := current.val
        current := current.next
        i := i + 1
    return result

Time: $O(n)$ per call. Space: $O(1)$. Each call traverses the entire list once.