本文共 1625 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一个链表头结点head，该链表节点的域除了有单链表节点的域之外，还有一个random域，可指向任意一个节点（包括自身）。链表节点数据结构如下：

class Node {    public int val;    public Node next;    public Node random;    public Node() {}    public Node(int _val,Node _next,Node _random) {        val = _val;        next = _next;        random = _random;    }};

现要求对该链表进行深度复制。例子：

思路：

与之前一个关于图的克隆问题思路一样： 也是使用dfs

代码：

class Solution {    public Node copyRandomList(Node head) {        if (head == null)            return null;        Map
   
     map = new HashMap<>();        Node node = new Node(head.val, null, null);        map.put(node.val, node);        dfs(head, node, map);        return node;    }    /*    如果该节点未被创建，则创建该节点的复制，并相应的域指向它，并从该节点开始继续进行dfs复制    如果该节点已被创建，则直接使相应的域指向它，不在该节点进行dfs复制    */    public void dfs(Node oldNode, Node newNode, Map
    
      map) {        if (oldNode.next != null) {            if (!map.containsKey(oldNode.next.val)) {                map.put(oldNode.next.val, new Node(oldNode.next.val, null, null));                newNode.next = map.get(oldNode.next.val);                dfs(oldNode.next, newNode.next, map);                } else {                newNode.next = map.get(oldNode.next.val);            }        }        if (oldNode.random != null) {            if (!map.containsKey(oldNode.random.val)) {                map.put(oldNode.random.val, new Node(oldNode.random.val, null, null));                newNode.random = map.get(oldNode.random.val);                dfs(oldNode.random, newNode.random, map);            } else {                newNode.random = map.get(oldNode.random.val);            }        }    }}
    
   

结果：

结论：

dfs。逻辑理清楚了就好做 

转载地址：http://sxesi.baihongyu.com/