复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

示例:

输入:

输出:

解析:我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。

以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5

后半部分，3，5，#，2，#分别的表示为

1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null

如下图:

示例

输入：
{1,2,3,4,5,3,5,#,2,#}
返回值：
{1,2,3,4,5,3,5,#,2,#}

代码

代码1 使用哈希表（实际就是一个map存储一下映射关系）

/*
使用哈希表
1. 先遍历一遍链表
2. 按顺序复制链表的每一项
3. 复制的同时将映射关系存在一个map中
4. 最后在遍历一遍map，将随机指针指向对应的位置
*/
function Clone(pHead)
{
    // write code here
    if(!pHead) return null
    
    // 定义一个虚拟头节点，用来保存新克隆的链表
    let dummy = new RandomListNode(-1) 
    let pre = dummy 
    let current = pHead
    
    // 定义一个map用来保存老节点与新节点的映射关系
    let map = new Map()
    
    while(current){
        // 克隆当前节点
        let cloneNode = new RandomListNode(current.label) 
        // 重新构造链表
        pre.next = cloneNode
        
        // 记录映射关系
        map.set(current, cloneNode)
        
        pre = pre.next
        current = current.next
    }
    // 上面的遍历一遍之后，只复制了next的节点，随机节点并没有复制上
    
    
    // 再遍历一遍map，把每个节点的随机指针附上值
    // 因为map已经保存了每个克隆节点的映射关系，所以根据映射关系，就能找到对应的random指针
    // map的key是老节点，value是新节点
    for(let oldNode of Array.from(map.keys())){
        let newCloneNode = map.get(oldNode)
        let newRandom = map.get(oldNode.random)
        newCloneNode.random = newRandom
    }
    
    return dummy.next
}

题目来源

JZ35 复杂链表的复制