题目描述
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例:
输入: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
思路
- 对要拷贝的链表进行两次遍历。
2.第一次遍历以原链表节点为key,新建节点为value将它们存储再哈希表中。
3.第二次遍历将新建的节点取出,并设置next和random节点。
Java代码实现
public Node copyRandomList(Node head) { Map<Node,Node> nodeMap = new HashMap(); Node p = head; while(p != null){ nodeMap.put(p,new Node(p.val)); p = p.next; } p = head; while(p != null){ nodeMap.get(p).next = nodeMap.get(p.next); nodeMap.get(p).random = nodeMap.get(p.random); p = p.next; } return nodeMap.get(head); }