题解 | #数据流中的中位数#

因为这道题是需要对数据流进行排序，所有用单向链表做题比较方便插入值。只需要记录下链表内已有的个数就可以很方便的得出中位数的值。代码比较简单易懂，欢迎修改。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型 
 * @return 无
 */
 typedef struct ChainNode{
    int val;
    struct ChainNode* Next;
 }ChainNode;

static ChainNode* Head;
static int Nnum=0;
void Insert(int num ) {
    ChainNode* NewNode=(ChainNode *)calloc(1,sizeof(ChainNode));
    NewNode->val=num;
    if(Nnum==0)
        Head=NewNode;
    else{
        if(num<Head->val){
            NewNode->Next=Head;
            Head=NewNode;
        }
        else{
            ChainNode* PreNode=Head;
            ChainNode* CurrNode=Head->Next;
            while(CurrNode!=NULL){
                if(num<=CurrNode->val)
                    break;
                PreNode=PreNode->Next;
                CurrNode=CurrNode->Next;
            }
            PreNode->Next=NewNode;
            NewNode->Next=CurrNode;
        }
    }  
    Nnum++;  
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return double浮点型
 */
double GetMedian() {
    printf("%d\n",Nnum);
    struct ChainNode* Temp=Head;
    int Index=Nnum/2;
    if(Nnum%2==1){
        for(int i=0;i<Index;i++)
            Temp=Temp->Next;
        return (double)Temp->val;
    }
    else {
        for(int i=0;i<Index-1;i++)
            Temp=Temp->Next;
        return (double)Temp->val/2+(double)Temp->Next->val/2;
    }
    
}