题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

哈希表

利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。

算法流程：

• 若头节点 head 为空节点，直接返回 nullnull ；
• 初始化： 哈希表 dic ， 节点 cur 指向头节点；
• 复制链表：
  • 建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） ；
  • cur 遍历至原链表下一节点；
• 构建新链表的引用指向：
  • 构建新节点的 next 和 random 引用指向；
  • cur 遍历至原链表下一节点；
• 返回值： 新链表的头节点 dic[cur] ；

复杂度分析：

• 时间复杂度 O(N)O(N) ： 两轮遍历链表，使用 O(N)O(N) 时间。
• 空间复杂度 O(N)O(N) ： 哈希表 dic 使用线性大小的额外空间。

注意最重要的是hashMap存储的键值对代表的含义，直接操作键值对。

/**
         * 哈希表
         * @param head
         * @return
         */
public Node copyRandomList(Node head) {
    Node cur = head;
    Map<Node, Node> map = new HashMap<>();  // key:需要复制的节点,value:新复制的节点
    while (cur != null) {   // 将所有值都放入map
        map.put(cur, new Node(cur.val));    // 新复制的节点都在value上
        cur = cur.next;
    }
    cur = head; // 重新
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);   // 返回头节点，也映射在了map中
}

拼接 + 拆分

考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。
算法流程：

• 复制各节点，构建拼接链表
• 构建新链表各节点的 random 指向：当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
• 拆分原 / 新链表：
  • 设置 pre / cur 分别指向原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
  • 返回新链表的头节点 res 即可。

复杂度分析：

• 时间复杂度 O(N)O(N) ： 三轮遍历链表，使用 O(N)O(N) 时间。
• 空间复杂度 O(1)O(1) ： 节点引用变量使用常数大小的额外空间。

/**
         * 拼接 + 拆分
         *
         * @param head
         * @return
         */
public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Node cur = head;
    // 复制各节点，并构建拼接链表
    while (cur != null) {
        Node node = new Node(cur.val);
        node.next = cur.next;
        cur.next = node;
        cur = node.next;
    }
    cur = head;
    // 拼接random域
    while (cur != null) {
        if (cur.random != null) {    // 注意判空
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }
    // 拆分2各链表
    cur = head.next;
    Node pre = head, res = head.next;
    while (cur.next != null) {  // 注意判空，取了2个next
        pre.next = pre.next.next;
        cur.next = cur.next.next;
        pre = pre.next;
        cur = cur.next;
    }
    pre.next = null;// 单独处理原链表尾节点
    return res;     // 返回新链表头节点
}