สุ่มโหนดใน Linked List ใน C++

ให้ singly linked list ต้องการสุ่มค่าของโหนดหนึ่งโหนด โดยทุกโหนดต้องมีโอกาสเท่ากัน (Reservoir Sampling บน linked list)

ตัวอย่าง: list [1,2,3] → สุ่มได้ 1, 2, หรือ 3 โอกาสเท่ากัน

ขั้นตอนการแก้ปัญหา (Reservoir Sampling)

1. เก็บ head ของ linked list
2. getRandom():
   • ret = -1, len = 1, curr = head
   • วนจน curr == null:
     • ถ้า rand() % len == 0 → ret = curr->val
     • len++, curr = curr->next
   • คืน ret

หลักการเดียวกับอาร์เรย์: โหนดที่ k มีโอกาส 1/k ถูกเลือก

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val; ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* p = head;
        while (p->next) p = p->next;
        p->next = new ListNode(v[i]);
    }
    return head;
}

class Solution {
public:
    ListNode* head;
    Solution(ListNode* h) { srand(time(NULL)); head = h; }
    int getRandom() {
        int ret = -1, len = 1;
        ListNode* cur = head;
        while (cur) {
            if (rand() % len == 0) ret = cur->val;
            len++; cur = cur->next;
        }
        return ret;
    }
};

int main() {
    vector<int> v = {1,7,4,9,2,5};
    Solution ob(make_list(v));
    cout << ob.getRandom();
}

Input

Initialize list with [1,7,4,9,2,5] Call getRandom() to get random nodes

Output

4 9 1