## 1. 问题描述

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.

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].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

## 2. 解题

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

typedef struct {
} Solution;

Note that the head is guaranteed to be not null, so it contains at least one node. */

Solution* sl = (Solution *)malloc(sizeof(Solution));
srand((unsigned int)time(NULL));

return sl;
}

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

// 依次向后
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);
}

Last modification：November 28th, 2021 at 07:57 pm