首页 > 代码库 > leetcode 138. Copy List with Random Pointer ----- java
leetcode 138. Copy List with Random Pointer ----- java
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.
和第133题差不多,都是图的复制,区别在于这道题的label有可能是相同的,所以导致了map的key有可能相同,所以需要处理。
两种方法差不多。第二种更简洁。
1、在复制next之后修改原结构的label为顺序增长,方便建立map,之后再修改回来。
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if( head == null ) return null; Map map2 = new HashMap<Integer,RandomListNode>(); int num = 1; RandomListNode node = head; RandomListNode newNode = new RandomListNode(head.label); RandomListNode node2 = newNode; map2.put(0,node2); node.label = 0; node = node.next; while( node != null ){ RandomListNode nextNode = new RandomListNode(node.label); node2.next = nextNode; node2 = node2.next; node.label = num; map2.put(num,node2); num++; node = node.next; } node = head; node2 = newNode; while( node != null ){ if( node.random == null){ node = node.next; node2 = node2.next; continue; } node2.random = (RandomListNode) map2.get( node.random.label ); node = node.next; node2 = node2.next; } node2 = newNode; node = head; while( node != null ){ node.label = node2.label; node = node.next; node2 = node2.next; } return newNode; } }
2、建立map的时候使用
Map<RandomListNode,RandomListNode>
/** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if( head == null ) return null; Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>(); RandomListNode node = head; while( node != null ){ map.put(node,new RandomListNode(node.label)); node = node.next; } node = head; while( node != null ){ map.get(node).next = map.get(node.next); map.get(node).random = map.get(node.random); node = node.next; } return map.get(head); } }
leetcode 138. Copy List with Random Pointer ----- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。