算法题记录——复杂链表的复制

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

初步解决

思路：由于题目中的链表节点有一个随机指针，所以从头节点按顺序复制的话，可能出现指向的随机节点还没有被复制的问题，故考虑先按顺序复制，并将指针都设为null，用哈希表保存每个节点对应的副本，再将节点的指针连起来

代码(js)：

const copyRandomList = function(head) {
    if(!head) { return null }
    let curr = head
    const nodeMap = new Map()
    while(curr) {
        nodeMap.set(curr, {val:curr.val, next:null, random:null})
        curr = curr.next
    }
    curr = head
    while(curr) {
        nodeMap.get(curr).next = nodeMap.get(curr.next) || null
        nodeMap.get(curr).random = nodeMap.get(curr.random) || null
        curr = curr.next
    }
    return nodeMap.get(head)
};

复杂度分析：这样做需要遍历两次初始链表，且需要哈希表保存原节点和对应副本节点，时间复杂度O(n)，空间复杂度O(n)

优化

思路：上面的思路中指向的随机节点还没有被复制可以用递归来解决，在一次遍历中直接复制节点，若节点的next或者random指针还没有被创建，则递归复制节点

代码(js)：

const copyRandomList = function(head, map = new Map()) {
    if(!head) { return null }
    if (!map.has(head)) {
        map.set(head, { val: head.val })
        Object.assign(map.get(head), {next: copyRandomList(head.next, map), random: copyRandomList(head.random, map)})
    }
    return map.get(head)
};

复杂度分析：与上面的代码相同，都需要遍历链表及创建哈希表，故复杂度都为O(n)

其他方法：迭代-节点拆分（个人认为方法虽然巧妙但不够简洁…）