class Node {
  constructor(value=0, next = null, random = null) {
    this.value = value;
    this.next = next;
    this.random = random;
  }
}

function clone(node) {
  if(node === null) return node;
  let current = node;

  //copy every node and insert to list
  while(current !== null) {
    let copy = new Node(current.value);
    copy.next = current.next;
    current.next = copy;
    current = copy.next;
  }

  //copy random pointer for each new node
  current = node;
  while(current !== null) {
    if(current.random !== null) {
      current.next.random = current.random.next;
    }
    current = current.next.next;
  }

  //break list into two
  current = node;
  let newHead = node.next;
  while(current !== null) {
    let temp = current.next;
    current.next = temp.next;
    if(temp.next !== null) {
      temp.next = temp.next.next;
    }
    current = current.next;
  }

  return newHead;
}

//Using Map
function clone(node) {
  if(node === null) return node;

  let map = new Map();
  let copy = new Node(node.value);
  let current = node;
  let newHead = copy;

  map.set(current, copy);

  current = current.next;
  while(current !== null) {
    let temp = new Node(current.value);
    map.set(current, temp);
    copy.next = temp;
    copy = temp;
    current = current.next;
  }

  current = node;
  copy = newHead;

  while(current !== null) {
    if(current.randome !== null) {
      copy.random = map.get(current.random);
    } else {
      copy.random = null;
    }

    current = current.next;
    copy = copy.next;
  }

  return newHead;
}

function print(node) {
  while(node !== null) {
      console.log(node.value + '=>' + node.random.value);
      node = node.next;
  }
}

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);

node1.next = node2;
node2.next = node3;
node3.next = null;
node1.random = node2;
node2.random = node2;
node3.random = node1;

print(clone(node1));