[LeetCode]Linked List Random Node

用Reservoir Sampling解即可，线性时间常数空间，代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	/** @param head The linked list's head.
	Note that the head is guaranteed to be not null, so it contains at least one node. */
	Solution(ListNode* head) {
	m_head = head;
	}
	/** Returns a random node's value. */
	int getRandom() {
	ListNode* curr = m_head;
	int count = 0, cand = 0;
	while(curr)
	{
	if(!count)
	cand = curr->val;
	else
	{
	int random = rand() % (count + 1);
	if(!random)
	cand = curr->val;
	}
	curr = curr->next;
	++count;
	}
	return cand;
	}
	private:
	ListNode* m_head;
	};
	/**
	* Your Solution object will be instantiated and called as such:
	* Solution obj = new Solution(head);
	* int param_1 = obj.getRandom();
	*/

view raw Linked List Random Node.cpp hosted with ❤ by GitHub