138.Copy_List_with_Random_Pointer

/**
 * 复制带随机指针的链表
 * @param {Node} head - 原始链表的头节点
 * @returns {Node} - 复制后的新链表的头节点
 * Node 节点结构：{ val: number, next: Node|null, random: Node|null }
 */
var copyRandomList = function (head) {
  // 边界条件：如果原始链表为空，直接返回null
  if (head === null) {
    return null
  }

  // ========== 第一步：在每个原始节点后面插入对应的复制节点 ==========
  // 遍历原始链表，node 从头部开始，每次向后移动两步（因为插入了新节点）
  for (let node = head; node !== null; node = node.next.next) {
    // 创建新节点：值和原始节点相同，next指向原始节点的下一个节点，random先设为null
    const nodeNew = new Node(node.val, node.next, null)
    // 将原始节点的next指向新创建的复制节点
    node.next = nodeNew
  }

  // ========== 第二步：设置复制节点的random指针 ==========
  // 再次遍历原始链表，为每个复制节点设置random指针
  for (let node = head; node !== null; node = node.next.next) {
    // 获取当前原始节点对应的复制节点
    const nodeNew = node.next
    // 核心逻辑：
    // 1. 如果原始节点的random不为null，那么复制节点的random就是原始节点random指向节点的下一个节点（即对应的复制节点）
    // 2. 如果原始节点的random为null，复制节点的random也为null
    nodeNew.random = node.random !== null ? node.random.next : null
  }

  // ========== 第三步：拆分两个链表（恢复原始链表，提取复制链表） ==========
  // 保存复制链表的头节点（原始头节点的下一个节点）
  const headNew = head.next
  // 遍历链表，拆分原始节点和复制节点
  for (let node = head; node !== null; node = node.next) {
    // 获取当前原始节点对应的复制节点
    const nodeNew = node.next
    // 恢复原始节点的next指针：指向下一个原始节点（跳过复制节点）
    node.next = node.next.next
    // 设置复制节点的next指针：
    // 1. 如果复制节点的next不为null，指向复制节点的下一个复制节点
    // 2. 如果复制节点的next为null，说明到链表末尾，设为null
    nodeNew.next = nodeNew.next !== null ? nodeNew.next.next : null
  }

  // 返回复制链表的头节点
  return headNew
}