## 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. 解题

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);
}

Last modification：September 8th, 2019 at 08:23 pm