[刷题笔记] 139 Copy List with Random Pointer

题目

思路过程

第一次失败

粗略扫了一边题目，准备用三个hashMap分别存储node，next关系，以及random关系。

第一次提交一看，Wrong Anwser，原来，每个Node的val可以相同，所以没办法单独用val来做hashMap的Key。

第二次失败

仔细分析，可以推敲到，如果每个old node能有一个指针指向new node，那么复制random关系的时候就是

newNode = currentOldNode.getNewNode()
newNode.random = currentOldNode.random.getNewNode()
newNode.next = currentOldNode.next.getNewNode()

那么我们需要重新定义一个class吗？那样还不如把node自身作为HashMap的Key算了。（最不动脑经的做法）

仔细一想，我们可以用old node的next指针指向new node，然后用一个数组按顺序保存old node。这样等我们建立好了new node之间random关系的同时，可以参照数组建立next关系。

def copyRandomList(head)
   arr = []
   return nil unless head
   current = head
   while current
       arr.push current
       next_node = current.next
       node = Node.new(current.val)
      # borrow it
       current.next = node
       current = next_node
   end
   head = arr[0].next
   for i in 0...arr.length
       if arr[i].random
         arr[i].next.random = arr[i].random.next
       else
         arr[i].next.random = nil   
       end
       if arr[i+1]
         arr[i].next.next = arr[i+1].next
       else
         arr[i].next.next = nil
       end
   end
    
   return head
end

提交，Wrong anwser。 一看提示，还是没有仔细审题。原来的old node之间的next 关系和 random关系不能改变。

当我们把next借来指向new node的时候，这个关系破坏了。好在我们有数组，可以用来恢复这个关系。

成功代码

def copyRandomList(head)
   arr = []
   return nil unless head
   current = head
   while current
       arr.push current
       next_node = current.next
       node = Node.new(current.val)
      # borrow it
       current.next = node
       current = next_node
   end
   head = arr[0].next
   for i in 0...arr.length
       if arr[i].random
         arr[i].next.random = arr[i].random.next
       else
         arr[i].next.random = nil   
       end
       if arr[i+1]
         arr[i].next.next = arr[i+1].next
       else
         arr[i].next.next = nil
       end
   end
    # recover
    for i in 0...arr.length
       if arr[i+1]
         arr[i].next = arr[i+1] 
       else
         arr[i].next = nil
       end
    end
    
   return head
end

反思

参考一下别人的做法，有一种是不需要建立数组。而是把 currentOld 的next 指向 currentNew，然后把currentNew的next指向nextOld。
这个方法不需要额外的数组保存顺序，只需要最后用两个指针把通过next连接在一起的新老list分成两个就好了。