#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <iostream>

struct listNode{
  int data;
  struct listNode *nextptr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

ListNodePtr create(const int W) { 
  assert(W >= 1            && "What are you thinking ?");
  ListNodePtr headPtr = (ListNodePtr)malloc(sizeof(ListNode));
  headPtr->data    = 0;
  headPtr->nextptr = NULL;
  ListNodePtr lastPtr = headPtr;
  for(int i=1;i<W;i++){
    ListNodePtr nowPtr = (ListNodePtr)malloc(sizeof(ListNode));
    nowPtr->data=i;
    nowPtr->nextptr=NULL; 
    lastPtr->nextptr=nowPtr;
        lastPtr=nowPtr;
  }
  return headPtr;
};

int ranX(ListNodePtr *headPtrPtr, const int W){
  assert(headPtrPtr != NULL && "Are you kidding me ?");
  assert(W >= 1             && "What are you thinking ?");
  ListNodePtr headPtr = *headPtrPtr;
  assert(headPtr != NULL    && "You want too much.");
  int r=rand()%W;
  ListNodePtr lastPtr = NULL;
  ListNodePtr nowPtr  = headPtr;
  for(int i=0; i<r && nowPtr->nextptr !=NULL;i++){
    lastPtr=nowPtr;
    nowPtr=nowPtr->nextptr;
  }
  int data = nowPtr->data;
  if (lastPtr == NULL) {
    *headPtrPtr = NULL;
  } else {
    lastPtr->nextptr = nowPtr->nextptr;
  }
        free(nowPtr);
  return data;
};

int main() {
  const int W = 10;
  ListNodePtr headPtr = create(W);
  for (int i = 0; i < W+1; ++i) {
    std::cout << ranX(&headPtr, W) << std::endl;
  }
  return 0;
}