/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
  Node* copyRandomList(Node* head) {
    if (!head) return head;
    auto* new_list_head = head; // A
    auto* new_list_curr_iter = new_list_head;

    // create A->A1->B->B1->C->C1->nullptr new nodes
    while (new_list_curr_iter) {
      auto* tmp = new_list_curr_iter->next;
      new_list_curr_iter->next = new Node(new_list_curr_iter->val, tmp, new_list_curr_iter->random); // A1
      new_list_curr_iter = tmp;
    }

    // update random pointers
    new_list_curr_iter = new_list_head;
    while (new_list_curr_iter) {
      new_list_curr_iter = new_list_curr_iter->next; // A1, B1 ...
      if (new_list_curr_iter->random)
        new_list_curr_iter->random = new_list_curr_iter->random->next;
      new_list_curr_iter = new_list_curr_iter->next;
    }

    // remove refs on original nodes
    auto* old_list_curr_iter = head; // A
    new_list_curr_iter = new_list_head->next; // A1
    new_list_head = new_list_head->next;
    while (new_list_curr_iter->next) {
      old_list_curr_iter->next = old_list_curr_iter->next->next;
      old_list_curr_iter = old_list_curr_iter->next;
      new_list_curr_iter->next = new_list_curr_iter->next->next;
      new_list_curr_iter = new_list_curr_iter->next;
    }

    old_list_curr_iter->next = nullptr;
    return new_list_head;
  }
};