第382题---Linked_list_random_node

• 题意描述

  • 给定一个单链表，返回单链表的随机结点，每一个结点的概率相同。假设链表非常大，不知道长度，不用额外的空间
    
    

• 思路1

  • 首先，求出链表的长度，生成随机数，模上链表长度，再从头遍历到指定的结点（错误）
    
    

• 思路2

  • 水库抽样的思想：从N个数里面抽n个数，每个概率一样。首先把前个数放到数组中，然后遍历n+1个数时，生成随机数（1，n+1）之间，如果（1，n）之间和这个index的数交换，如果（n+1），则不换，类推
  • 本题目只返回一个数，则数组为1
    
    

• 代码

  /**
   * 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) {
          temp = head;
      }
      
      /** Returns a random node's value. */
      int getRandom() {
          int res;
          int len = 1;
          ListNode* tmp = temp;
          while(tmp) {
              if(rand() % len == 0)
                  res = tmp->val;
              len ++;
              tmp = tmp->next;
          }
          return res;
      }
  private:
      ListNode* temp;
  };
  
  /**
   * Your Solution object will be instantiated and called as such:
   * Solution obj = new Solution(head);
   * int param_1 = obj.getRandom();
   */