作者:whisper
链接:https://www.proprogrammar.com/article/921
声明:请尊重原作者的劳动,如需转载请注明出处
请实现 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 。
难度:中等;相关标签:链表;编程语言:JAVA
/*
// 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 {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>(); //创建HashMap集合
Node cur=head;
//复制结点值
while(cur!=null){
//存储put:<key,value1>
map.put(cur,new Node(cur.val)); //顺序遍历,存储老结点和新结点(先存储新创建的结点值)
cur=cur.next;
}
//复制结点指向
cur = head;
while(cur!=null){
//得到get:<key>.value2,3
map.get(cur).next = map.get(cur.next); //新结点next指向同旧结点的next指向
map.get(cur).random = map.get(cur.random); //新结点random指向同旧结点的random指向
cur = cur.next;
}
//返回复制的链表
return map.get(head);
}
}
首先映射所有旧节点与相应新节点,然后关联所有next与random
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论