未知长度链表中随机取出其中某一节点的值

转自：

 

题目描述：有一个单向链表的长度未知，怎样从中随机取出一个节点？要求每个节点被选中的概率相等。

解决方法：

   遍历一次链表，用一个临时变量pTemp指向返回的节点，设一个计数器iCount统计已遍历的节点个数，然后生成0到iCount-1之间的随机数；若生成的随机数为0，则将pTemp指针替换为当然节点的地址。可以证明对每一个节点，它被选中的概率为1/n，n为链表的长度。

    对于第i个节点，被选中的概率为:p = 1/i *(i  /i+1)*(i+1  /  i+2)*......(n-1  / n) = 1/n

代码如下：

 

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

struct Node
{
    int iVal;
    Node* next;
};

Node* GetOneNode(Node* head)
{
    if(head == NULL)
        return NULL;
    int iCount = 1;
    Node* tmp = head->next;
    Node* pRet = tmp;
    while(tmp)
    {
        int ran = rand();
        int t = ran%iCount;//生成0到iCount-1之间的一个随机数
        if(t == 0)
            pRet = tmp;
        iCount++;
        tmp = tmp->next;
    }
    return pRet;
}

Node* initLinkList(Node* head, int N)
{
    Node* p = NULL;
    Node* pTemp = head;
    for(int i=0; i<N; i++)
    {
        p = new Node;
        p->iVal = rand();
        p->next = NULL;
        pTemp->next = p;
        pTemp = p;
    }
    return head;
}

bool freeList(Node* head)
{
    Node* p = head;
    while(head)
    {
        p = head->next;
        delete head;
        head = p;
    }
    return true;
}

int main()
{
    Node* head = new Node;
    head = initLinkList(head, 10);
    Node* pRet = GetOneNode(head);
    cout<<pRet->iVal<<endl;
    freeList(head);
    return 0;
}