给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:

如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:

// 初始化一个单链表 [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()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。

solution.getRandom();

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

C++：

方法一：

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

 方法二：

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

 参考：https://www.cnblogs.com/grandyang/p/5759926.html