LeetCode 382. Linked List Random Node

描述

实现链表成员函数，该函数使得获取每一个节点值的概率相等。

解决

 /**
 * 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. */
    ListNode* tmp;
    Solution(ListNode* head) {
        tmp = head;
    }

   /** Returns a random node's value. */
   int getRandom() {
       int cnt = 1, res = 0;
       ListNode* tNode = tmp;
       while (tNode)
       {
           int t = rand() % cnt;
           if (t == 0)
           {
               res = tNode -> val;
           }
           tNode = tNode -> next;
           ++cnt;
       }
       return res;
   }
};

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