剑指 Offer 35. 复杂链表的复制

一：题目描述：

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

二：示例

示例1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

三：思路

`哈希表`

定义一个哈希表，用于存储每个节点的拷贝节点，键为原始节点，值为拷贝节点。
定义一个指针 cur，从头节点开始遍历原始链表。
在遍历原始链表时，对于一个原始节点 cur，创建一个与其值相同的新节点 copy，并将 cur 和 copy 存入哈希表中。
将 cur 的 next 指针指向 cur.next 的拷贝节点，如果 cur.random 不为空，则将 cur.random 指针指向 cur.random 的拷贝节点。
将 cur 指针向后移动一位，重复步骤 4 直到遍历结束。
最后返回哈希表中存储的头节点的拷贝即可。

`图解`

四：代码

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    //map()方法
    //1.先复制结点
    //2.next
    //3.random
    if(head === null){
        return head
    }
    var cur = head
    var map = new Map()

    //复制结点
    while(cur){
        //构建哈希表
        map.set(cur , new Node(cur.val))
        cur = cur.next
    }

    cur = head

    //2.3步 构建next,random指针指向
    while(cur){
        //next指针构建
        map.get(cur).next = map.get(cur.next) === undefined ? null : map.get(cur.next)
        //random指针构建
        map.get(cur).random = map.get(cur.random) === undefined ? null : map.get(cur.random)
        cur = cur.next
    }
    return map.get(head)
};

剑指 Offer 35. 复杂链表的复制

一：题目描述：

二：示例

示例1：

示例2：

示例3：

示例4：

提示：

三： 思路

哈希表

图解

四： 代码

三：思路

`哈希表`

`图解`

四：代码