382. 链表随机节点

 1 class Solution 
 2 {
 3 public:
 4     ListNode* nod;
 5     Solution(ListNode* head) 
 6     {
 7         this->nod = head;
 8     }
 9 
10     int getRandom() 
11     {
12         if(nod == NULL) return 0;
13         int res = nod->val;//第一步选中1个数
14         ListNode* cur = nod;
15         
16         int ind = 1; //当前的个数
17         while(cur->next != NULL)
18         {
19             cur = cur->next;
20             if((rand()%(ind + 1)) == ind) res = cur->val;
21             ind ++;
22         }
23         return res;
24     }
25 };