Linked List Random Node解题报告

Description:

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();

Link:

https://leetcode.com/problems/linked-list-random-node/description/

解题方法：

当链表长度已知并且能放入内存中，通常我们可以采取将链表数据储存到数组当中O(N)，然后每次在O(1)时随机获取其中的数。
当链表长度巨大并且长度未知，此时我们需用另一个算法每次以O(N)时间来随机抽取：水塘抽样

Tips:

水塘抽样的算法证明过程其实更为复杂，在本题中，水塘的容量可看为1。

完整代码：

class Solution 
{
private:
    ListNode* head;
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) 
    {
        this->head = head;
    }  
    /** Returns a random node's value. */
    int getRandom() 
    {
        ListNode* curr = head;
        int rsv = curr->val;
        curr = curr->next;
        int j = 1;
        while(curr != NULL)
        {
            int r = rand() % (j + 1);
            if(r < 1)
                rsv = curr->val;
            j++;
            curr = curr->next;
        }
        return rsv;
    }
};