Leetcode 382 Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* m_head;
    int m_n;
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) {
        m_head = head;

        m_n = 0;

        while (head)
        {
            m_n++;
            head = head->next;
        }
    }

    /** Returns a random node's value. */
    int getRandom() {
        ListNode* p = m_head;
        int left_nodes = m_n;

        while (p)
        {
            if (rand() % left_nodes == 0)
                return p->val;

            p = p->next;
            left_nodes--;
        }

        return 0;
    }
};

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