Node *copyList(Node *head)
{
  for (Node* cur = head; cur != NULL; cur = cur->next) {
    Node* dup = (Node*)malloc(sizeof(Node));
    dup->data = cur->data;
    dup->next = cur->random;
    cur->random = dup;
  }
  Node* result = head->random;
  for (Node* cur = head; cur != NULL; cur = cur->next) {
    Node* dup = cur->random;
    dup->random = dup->next->random;
  }
  for (Node* cur = head; cur != NULL; cur = cur->next) {
    Node* dup = cur->random;
    cur->random = dup->next;
    dup->next = cur->next ? cur->next->random : NULL;
  }
  return result;
}