[LeetCode] Linked List Random Node 链表随机节点

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


class Solution {
public:
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
len = 0;
while (cur) {
++len;
cur = cur->next;
}
}

/** Returns a random node's value. */
int getRandom() {
int t = rand() % len;
while (t) {
--t;
cur = cur->next;
}
return cur->val;
}
private:
int len;
};

class Solution {
public:
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
}

/** Returns a random node's value. */
int getRandom() {
int res = head->val, i = 2;
while (cur) {
int j = rand() % i;
if (j == 0) res = cur->val;
++i;
cur = cur->next;
}
return res;
}
private:
};

|
2天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
32 17
|
2天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
35 14
|
1天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
10 5
|
4天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
15 5
|
7天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
20 7
|
9天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
12 1
|
11天前
|
JavaScript
DOM 节点列表长度（Node List Length）
DOM 节点列表长度（Node List Length）
12 1
|
3月前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
33 0
|
3月前
|

LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
32 2
|
3月前
|

【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
27 2