138-复制带随机指针的链表

138. 复制带随机指针的链表

拿到题目的想法是使用双指针指向新旧节点，再加上一个 map 用来映射旧节点和新节点。

递归

var listMap = new Map()
var copyRandomList = function(head) {
    if(head === null) return head
    if (listMap.get(head)) {
        return listMap.get(head)
    }
    let newNode = new Node(head.val,null,null)
    listMap.set(head, newNode)
    newNode.next = copyRandomList(head.next)
    newNode.random = copyRandomList(head.random)
    return newNode
};

迭代

var copyRandomList = function(head) {
    if(head == null) return head
    var listMap = new Map()
    listMap.set(null,null)
    var cur = head
    while (cur!= null) {
        listMap.set(cur,new Node(cur.val,null,null))
        cur = cur.next
    }
    cur = head
    while (cur!= null) {
        listMap.get(cur).next = listMap.get(cur.next)
        listMap.get(cur).random = listMap.get(cur.random)
        cur = cur.next
    }
    return listMap.get(head)
};