西安php网站制作,暴走漫画网站建设中模板,大连工业大学怎么样,房地产网站开发公司电话题目
请实现 copyRandomList 函数#xff0c;复制一个复杂链表。在复杂链表中#xff0c;每个节点除了有一个 next 指针指向下一个节点#xff0c;还有一个 random 指针指向链表中的任意节点或者 null。 示例 1#xff1a; 输入#xff1a;head [[7,null],[13,0],[11,4]…题目
请实现 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 10000Node.random 为空null或指向链表中的节点。节点数目不超过 1000 。 解答
源代码
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val val;this.next null;this.random null;}
}
*/
class Solution {MapNode, Node map new HashMap();public Node copyRandomList(Node head) {if (head null) {return null;}if (!map.containsKey(head)) {Node cur new Node(head.val);map.put(head, cur);cur.next copyRandomList(head.next);cur.random copyRandomList(head.random);}return map.get(head);}
}
总结
一开始低估了问题复杂性了以为遍历两次就可以了一次把节点、链表创建出来第二次遍历把random指针也设置好。但是实际操作的时候发现第二次遍历时虽然可以得到原链表节点的random指针指向的节点但是复制出来的这个链表节点的random指针应该指向的节点丢了。
学习了题解用了回溯算法方法输入的是原链表的节点返回的是复制出来的链表的对应节点。
