Nút ngẫu nhiên danh sách liên kết trong C++

Mô tả bài toán

Cho danh sách liên kết đơn. Triển khai getRandom() trả về giá trị nút ngẫu nhiên với xác suất đều nhau (1/n).

Ví dụ: Danh sách [1,7,4,9,2,5] → getRandom() trả về ngẫu nhiên 1 trong 6 giá trị.

Giải thuật Reservoir Sampling (k=1)

Duyệt danh sách, biến len đếm số nút đã thấy. Tại nút thứ len, chọn nó với xác suất 1/len (rand() % len == 0). Đảm bảo mỗi nút có xác suất 1/n.

Cài đặt C++

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

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

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

class Solution {
    ListNode* head;
public:
    Solution(ListNode* head) : head(head) { srand(time(nullptr)); }
    int getRandom() {
        int res = -1, len = 0;
        for (ListNode* p = head; p; p = p->next) {
            if (rand() % ++len == 0) res = p->val;
        }
        return res;
    }
};

int main() {
    ListNode* h = make_list({1,7,4,9,2,5});
    Solution ob(h);
    for (int i = 0; i < 3; i++) cout << ob.getRandom() << ' '; // ví dụ: 4 9 1
    return 0;
}

Độ phức tạp

• Thời gian: O(n) mỗi lần gọi.
• Không gian: O(1) (không lưu mảng).