Copy list with Random Pointer

Leave a comment

October 31, 2016 by oneOokay

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.


所以这题呢其实就是考的一个deepcopy的问题。deepcopy都会涉及到用一个hashmap<K,V>来存旧的值和新的值的对应关系。以及考虑不重复create node。

另外他这个random指针是加在next的基础上的,所以所有的RandomListNode都可以被next指针access到,不存在一个RandomListNode仅能够被random指到而不能被next指到。

所以如果用HashMap的话非常简单:

  • 一个while loop完所有的node,建立一个Map。
  • 第二个while loop把next和random指针建立好就可以了。
  • 这里不需要用到Queue是因为linkedlist的特性是所有的点都是通过.next连成一串的. 所以一次while loop就可以遍历复制完所有的点.
public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null) return null;
  Map<RandomListNode, RandomListNode> map = 
  new HashMap<RandomListNode, RandomListNode>();
  // loop 1. copy all the nodes
  RandomListNode node = head;
  while (node != null) {
    map.put(node, new RandomListNode(node.label));
    node = node.next;
  }
  
  // loop 2. assign next and random pointers
  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);
}

无HASHMAP:

如果是不用hashmap的话,就也要经历:新建new nodes然后copy他们的关系的步骤:

  1. 一个while loop把新的node插入到旧的node和node.next之间(这里就已经copy的next指针的关系,所以不需要额外的一步)
  2. 复制random指针的关系:while loop,把new node的random指针指向新的new node
  3. 分割:把new nodes和旧nodes 分割成两个独立的linkedlist。这里是一定要进行分割开的
  4. 还要注意null check
public RandomListNode copyRandomList(RandomListNode head) {
 if (head == null) return head;
 RandomListNode cur = head;
//创建新的node:把新的node插入在原node和原node.next之间:
//原:Node1->Node2
//新:Node1->NewNode1->Node2->newNode2
 while (cur != null){
   RandomListNode tmp = new RandomListNode(cur.label);
   tmp.next = cur.next;
   cur.next = tmp;
   cur = tmp.next;
 }
 //复制random指针关系
 cur = head;
 while (cur != null){
 RandomListNode tmp = cur.next;//tmp为newNode
 if (cur.random != null)//注意null chuck
 tmp.random = cur.random.next;
 cur = tmp.next;
 }
 //分割list
 cur = head;
 RandomListNode dummy = head.next;//已经知道了新head,因为在分割list之后
//就不能够通过原head找到新的head了,所以这里存一下
 while (cur != null){
 RandomListNode tmp = cur.next;
 cur.next = tmp.next;//原node跳过newNode,重新直接指向自己的next
 if (tmp.next != null){//null check
 tmp.next = tmp.next.next;//新node跳过旧node,直接指向新的node
 }
 cur = cur.next;//分割完list之后,cur.next就直接是下一个还未分割的旧node
 }
 return dummy;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: