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; }