382. Linked List Random Node

  • 46.4%

https://leetcode.com/problems/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.

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?

1
2
3
4
5
6
7
8
9
10
11
> 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();
>

java

136ms, September 11, 2016

https://discuss.leetcode.com/topic/53738/o-n-time-o-1-space-java-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {

ListNode head = null;
Random randomGenerator = null;
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
public Solution(ListNode head) {
this.head = head;
this.randomGenerator = new Random();
}

/** Returns a random node's value. */
public int getRandom() {
ListNode result = null;
ListNode current = head;

for(int n = 1; current != null; n++){
if(randomGenerator.nextInt(n) == 0){
result = current;
}
current = current.next;
}
return result.val;
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/

cpp

72ms, September 11, 2016

https://discuss.leetcode.com/topic/53812/using-reservoir-sampling-o-1-space-o-n-time-complexity-c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode* head;

public:
/** @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(ListNode* head) {
this->head = head;
}

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

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/

python

375ms, September 12, 2016

https://discuss.leetcode.com/topic/53736/o-1-space-python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):

def __init__(self, head):
"""
@param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node.
:type head: ListNode
"""
self.head = head

def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
import random
res = -1
len = 0
head = self.head
while head:
if random.randint(0, len) == 0:
res = head.val
head = head.next
len += 1
return res



# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
谢谢你,可爱的朋友。