#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/probability-basics/linked-list-random-node-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/probability-basics/linked-list-random-node-implementation

Repovive

Linked List Random Node - Implementation - Probability Basics | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Linked List Random Node - Implementation

The pseudocode

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.