力扣学习笔记——138. 随机链表的复制

解题思路

使用递归回溯的特性，可以直接将一个新结点完美拼接，不论是否初始化。

图解：

实现代码

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

复杂度分析

• 时间复杂度：O(N)
  • 遍历了链表长度，因为哈希表的缘故，第二次递归基本都是跳过遍历
• 空间复杂度：O(N)
  • 哈希表记录了链表长度