leetcode之Linked List Random Node

这题本身来讲是比较简单的。把所有的值放进一个list里，想取哪个取哪个。

import random # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def __init__(self, head): """ @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. :type head: ListNode """ self.list1 = [] while head: self.list1.append(head.val) head = head.next def getRandom(self): """ Returns a random node's value. :rtype: int """ location = random.randint(1, len(self.list1)) return self.list1[location - 1]

但是这样是要花费额外时间的，如果按照题目要求的那样，不花费额外的话，做法就相当于每个node都roll个点，roll完一遍之后，谁的点大谁就胜出。