# 382. Linked List Random Node 链表随机节点

@TOC

## # 题目描述

Given a singly linked list, return a random node's value from the linked list. Each node must have the `same probability` of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

``````Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();
``````

## # 解题方法

### # 数组保存再随机选择

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):

"""
Note that the head is guaranteed to be not null, so it contains at least one node.
"""
self.stack = []

def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
_len = len(self.stack)
return self.stack[random.randint(0, _len - 1)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
``````

### # 蓄水池抽样

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
Note that the head is guaranteed to be not null, so it contains at least one node. */
}

/** Returns a random node's value. */
int getRandom() {
ListNode* head = h_;
int cnt = 0, res = 0;
++cnt;
if (rand() % cnt == 0)
}
return res;
}
private:
ListNode* h_;
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
``````

## # 日期

2018 年 3 月 8 日 2019 年 2 月 26 日 —— 二月就要完了