Code & Func

第90天。

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

写出了一个朴素的解法，两次扫描：

1
Solution(ListNode* p) {
2
    len = 0;
3
    head = p;
4
    while(p) {
5
        len++;
6
        p = p->next;
7
    }
8
    cout << len << endl;
9
}
10

11
/** Returns a random node's value. */
12
int getRandom() {
13
    int r = rand() % len;
14
    cout << r << endl;
15
    ListNode *p = head;
7 collapsed lines
16
    while(r-- && p) {
17
        p = p->next;
18
    }
19
    return p->val;
20
}
21
int len;
22
ListNode *head;

然后是利用栈来做的一个解法，即一直递归调用直到链表结尾，这时我们已经遍历了一遍链表就可以知道其长度了，在这时生成随机数，然后在递归调用返回的时候通过这个随机数来选取节点：

1
int getRandom() {
2
    temp_len = 0;
3
    getRandom(head);
4
    return res;
5
}
6
bool getRandom(ListNode *p) {
7
    if (p == nullptr) {
8
        rand_n = rand() % temp_len;
9
        return false;
10
    }
11
    temp_len++;
12
    if(getRandom(p->next)) return true;
13
    if (rand_n == 0) {
14
        res = p->val;
15
        return true;
8 collapsed lines
16
    }
17
    rand_n--;
18
    return false;
19
}
20
int temp_len;
21
int rand_n;
22
ListNode *head;
23
int res;

最后是dicuss中的水库抽样法：

1
int getRandom() {
2
    int res = head->val;
3
    ListNode* node = head->next;
4
    int i = 2;
5
    while(node){
6
        int j = rand()%i;
7
        if(j==0)
8
            res = node->val;
9
        i++;
10
        node = node->next;
11
    }
12
    return res;
13
}

证明可参考：http://blog.csdn.net/so_geili/article/details/52937212