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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 |
/** * 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) { RandomListNode newHead = new
RandomListNode(0); Map<RandomListNode, RandomListNode> oldToNew = new
HashMap<RandomListNode, RandomListNode>(); Map<RandomListNode, RandomListNode> newToOld = new
HashMap<RandomListNode, RandomListNode>(); if(head != null){ RandomListNode nextNode = head; RandomListNode nextNewNode = newHead; while(nextNode != null){ nextNewNode.next = new
RandomListNode(nextNode.label); nextNewNode = nextNewNode.next; oldToNew.put(nextNode, nextNewNode); newToOld.put(nextNewNode, nextNode); nextNode = nextNode.next; } nextNewNode.next = null; nextNewNode = newHead.next; while(nextNewNode != null){ RandomListNode tempOld = newToOld.get(nextNewNode); RandomListNode tempnew = oldToNew.get(tempOld.random); nextNewNode.random = tempnew; nextNewNode = nextNewNode.next; } } newHead = newHead.next; return
newHead; }} |
leetcode--Copy List with Random Pointer
原文：http://www.cnblogs.com/averillzheng/p/3565856.html