struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

vector<int> getRandom(ListNode* head, int k) {
  vector<int> res(k);
  int count = 0;
  ListNode* curr = head;
  while(curr)
  {
    if(count < k)res[count] = curr->val;
    else
    {
      int random = rand() % (count + 1);
      if(random < k)res[random] = curr->val;
    }
    curr = curr->next;
    ++count;
  }
  return res;
}