1. 问题描述

problem link

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

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?

Example:

// Init a singly linked list [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() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

2. 解题

首先了解蓄水池采样算法

很明显，可以用蓄水池采样算法解决这个问题，在这个问题中k = 1，具体代码如下:

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct {
    struct ListNode* head;
} Solution;

/** @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* solutionCreate(struct ListNode* head) {
    Solution* sl = (Solution *)malloc(sizeof(Solution));
    sl->head = head;
    srand((unsigned int)time(NULL));

    return sl;
}

/** Returns a random node's value. */
int solutionGetRandom(Solution* obj) {
    // 首先将结果初始化成第一个元素
    int res = obj->head->val;

    // 依次向后
    struct ListNode* cur = obj->head->next;
    int count = 2;
    int tmp;
    
    while (cur != NULL) {
        tmp = rand() % count;  // 0 ~ count-1
        if (tmp == 0) {  // 这里把0换成任意一个0 ~ count-1的数都行，选到的概率都是一样的
            res = cur->val;
        }
        cur = cur->next;
        count++;
    }

    return res;
}

void solutionFree(Solution* obj) {
    free(obj);
}