Python solution with detailed explanation


  • 0
    G

    Solution with detailed explanation https://leetcode.com/problems/linked-list-random-node/

    Linked List Random Node https://leetcode.com/problems/linked-list-random-node/

    Algorithm

    • Select first node with p = 1
    • Select second node with p = 1/2
    • Select kth node with p = 1/k
    • Let P(k) be the probability of selecting kth node.
    • Probability of kth node being selected after we have seen N elements (N>k) = P(k) * (1-P(k+1)) * (1-P(k+2)) * ... (1 - 1/N) = 1/N
    from random import randint
    class Solution(object):
        def __init__(self, head):
            """
            @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
            :type head: ListNode
            """
            self.head = head
    
        def getRandom(self):
            """
            Returns a random node's value.
            :rtype: int
            """
            rnode, count = None, 1
            root = self.head
            while root:
                if randint(1, count) == 1:
                    rnode = root
                root, count = root.next, count + 1
            return rnode.val
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.