剑指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 。

**注意：**本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

Related Topics

• 哈希表
• 链表

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

复制的时候，不确定 next、random 节点是否已经被创建了

题解

回溯+哈希表

• 用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况
• 如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。
• 当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。
• 由于一个节点可能会被多个节点指向，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

class Solution {
    
    Map<Node,Node> cacheNodes = new HashMap<>();
    public Node copyRandomList(Node head) {
    
        if (head == null){
    
            return null;
        }
        if (!cacheNodes.containsKey(head)){
    
            Node headNew = new Node(head.val);
            cacheNodes.put(head,headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cacheNodes.get(head);
    }
}

迭代+节点分拆

• 将每一个节点之后加一个响应的复制的节点，即：A→B→C ==》 A→A′→B→B′→C→C′
• 这样子，每个节点的随机节点就都建立成功了
• 这样，我们可以直接找到每一个拷贝节点 S′ 的随机指针应当指向的节点，即为其原节点 S 的随机指针指向的节点 T 的后继节点 T′。
• 当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。

class Solution {
    
    Map<Node,Node> cacheNodes = new HashMap<>();
    public Node copyRandomList(Node head) {
    
        if (head == null){
    
            return null;
        }
        //复制每个节点
        for (Node node = head;node != null;node = node.next.next){
    
            Node copyNode = new Node(node.val);
            copyNode.next = node.next;
            node.next = copyNode;
        }
        //链表的分割
        //随机节点的复制
        for (Node node = head;node != null;node = node.next.next){
    
            Node copyNode = node.next;
            copyNode.random = (node.random == null) ? null : node.random.next;
        }
        //后继节点的复制
        Node newNode = head.next;
        for (Node node = head;node != null;node = node.next){
    
            Node copyNode = node.next;
            node.next = node.next.next;
            copyNode.next = (copyNode.next == null) ? null : copyNode.next.next;
        }
        return newNode;
    }
}