LeetCode[138] Copy List with Random Pointer
文章目录
LeetCode[138] Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list
Map
复杂度
O(N), O(N)
思路
和clone graph一样的思路。先copy顺序的,再copy那些random的pointer.
代码
public RandomListNode copyRandomList(RandomListNode node) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode dummy = new RandomListNode(0);
RandomListNode p = head, q = head;
// used to connect the new list;
RandomListNode phead = dummy;
while(p != null) {
RandomListNode cp = new RandomListNode(p.label);
map.put(p, cp);
p = p.next;
phead.next = cp;
phead = phead.next;
}
while(q != null) {
map.get(q).random = map.get(q.random);
q = q.next;
}
return dummy.next;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论