# Leetcode 382. Linked List Random Node
###### tags: `leetcode` `daily` `Linked List` `random`

[題目連結](https://leetcode.com/problems/linked-list-random-node/description/)

### **Follow up:**
###### **What if the linked list is extremely large and its length is unknown to you?**
###### **Could you solve this efficiently without using extra space?**

# Method
:::info
:bulb: **作法講解**:

由於題目說明 Linked list數量可能會很大,
因此如果在建構子做亂數排列可能會超時,

這時候我們只能從 getRandom function 下手,
我們可以每次都取固定數量的node出來做亂數排列.
雖然這樣沒辦法達到**整體的隨機排列**,
不過可以完成**部分隨機排列**
:::

TC: O(N) SC: O(1)
完整程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> v;
    int next_idx = 0;
    ListNode* root;
    ListNode* cur;
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    Solution(ListNode* head) {
        v.assign(256, 0);
        root = head;
        cur = head;
        generate_next_round();
    }
    
    void generate_next_round() {
        for(int i = 0 ; (i < 256) ; i++) {
            v[i] = cur->val;
            cur = (cur->next) ? cur->next : root;
        }
        random_shuffle(v.begin(), v.end());
    }

    int getRandom() {
        int val = v[next_idx];

        next_idx++;
        if(next_idx == v.size()) {
            generate_next_round();
            next_idx = 0;
        }
        return val;
    }
};

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

:::