main.cpp

// Source: https://leetcode.com/problems/copy-list-with-random-pointer
// Title: Copy List with Random Pointer
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// A linked list of length `n` is given such that each node contains an additional random pointer, which could point to any node in the list, or `null`.
//
// Construct a **deep copy** (https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list. The deep copy should consist of exactly `n` **brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the `next` and `random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. **None of the pointers in the new list should point to nodes in the original list**.
//
// For example, if there are two nodes `X` and `Y` in the original list, where `X.random --> Y`, then for the corresponding two nodes `x` and `y` in the copied list, `x.random --> y`.
//
// Return the head of the copied linked list.
//
// The linked list is represented in the input/output as a list of `n` nodes. Each node is represented as a pair of `[val, random_index]` where:
//
// - `val`: an integer representing `Node.val`
// - `random_index`: the index of the node (range from `0` to `n-1`) that the `random` pointer points to, or `null` if it does not point to any node.
//
// Your code will **only** be given the `head` of the original linked list.
//
// **Example 1:**
// https://assets.leetcode.com/uploads/2019/12/18/e1.png
//
// ```
// Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
// Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
// ```
//
// **Example 2:**
// https://assets.leetcode.com/uploads/2019/12/18/e2.png
//
// ```
// Input: head = [[1,1],[2,1]]
// Output: [[1,1],[2,1]]
// ```
//
// **Example 3:**
//
// **https://assets.leetcode.com/uploads/2019/12/18/e3.png
//
// ```
// Input: head = [[3,null],[3,0],[3,null]]
// Output: [[3,null],[3,0],[3,null]]
// ```
//
// **Constraints:**
//
// - `0 <= n <= 1000`
// - `-10^4 <= Node.val <= 10^4`
// - `Node.random` is `null` or is pointing to some node in the linked list.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <unordered_map>

using namespace std;

class Node {
 public:
  int val;
  Node* next;
  Node* random;

  Node(int val) : val(val), next(nullptr), random(nullptr) {}
};

// Use hashmap
class Solution {
 public:
  Node* copyRandomList(Node* head) {
    auto nodeMap = unordered_map<Node*, Node*>();  // from old to new node

    // Helper
    auto getNode = [&](Node* oldNode) -> Node* {
      if (oldNode == nullptr) return nullptr;

      // Get existing node
      auto it = nodeMap.find(oldNode);
      if (it != nodeMap.cend()) return it->second;

      // Create new node
      auto newNode = new Node(oldNode->val);
      return nodeMap[oldNode] = newNode;
    };

    // Loop
    auto node = head;
    while (node != nullptr) {
      auto newNode = getNode(node);
      newNode->next = getNode(node->next);
      newNode->random = getNode(node->random);
      node = node->next;
    }

    return getNode(head);
  }
};

// Three-Pass
//
// For first loop, create new nodes (store in old->next and set new->next to the real next)
// For second loop, set the random pointer for the new nodes.
// For third loop, set the next pointer for the new nodes, and restore old->next.
class Solution2 {
 public:
  Node* copyRandomList(Node* head) {
    if (head == nullptr) return head;

    // First pass
    for (auto node = head; node != nullptr; node = node->next->next) {
      auto next = node->next;
      auto newNode = new Node(node->val);
      node->next = newNode;  // node->new = new
      newNode->next = next;  // new->next = next
    }
    auto newHead = head->next;

    // Second pass
    for (auto node = head; node != nullptr; node = node->next->next) {
      if (node->random) {
        node->next->random = node->random->next;  // new->random = random->new
      }
    }

    // Third pass
    for (auto node = head; node != nullptr; node = node->next) {
      auto next = node->next->next;
      if (next) {
        node->next->next = next->next;  // new->next = next->new
      }
      node->next = next;
    }

    return newHead;
  }
};