/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
import java.util.HashMap;
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null)
return null;
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
RandomListNode cur = head;
RandomListNode headCopy = new RandomListNode(head.label),curCopy=headCopy;
map.put(cur, headCopy);
cur = cur.next;
while(cur != null){
RandomListNode temp = new RandomListNode(cur.label);
curCopy.next = temp;
curCopy = temp;
map.put(cur, curCopy);
cur = cur.next;
}
cur = head;
curCopy = headCopy;
while(cur != null){
if(cur.random!=null)
curCopy.random = map.get(cur.random);
cur = cur.next;
curCopy = curCopy.next;
}
return headCopy;
}
} 题目描述
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.
