Copy List with Random Pointer

题目描述

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

所有的类似deep copy的题目，传统做法是用一个hashtable

  • 先按照正常的方法复制，将Label设为正确的值
  • 这一次新node的random pointer是指向旧node的random pointer指向的地方
  • 并且用复制的时候用hashtable记录下random pointer， 旧node为key,新node为value， 这样在下一次遍历时就可以将新node的random pointer指到新的node
  • 在second loop中根据Map里面保存的value来设正确的random pointer

time conplexity: O(n), space complexity: O(n)

方法2

  • first loop, copy每一个Node, 并且加在原Node的后面，random pointer指向原来的node
  • second loop, 将偶数位置的node的random pointer指向原来node的后面一位
  • third loop, split the list，将偶数位置的点变成一个新的list

Solution

方法1

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return 

        dummy = RandomListNode(0)
        pre = dummy
        nodeMap = {}

        # first loop
        # set label
        # set random pointer point to the same old node
        # save {old node: new node} pair in map, for use in next loop
        while head:
            newNode = RandomListNode(head.label)
            newNode.random = head.random
            nodeMap[head] = newNode
            pre.next = newNode
            pre = pre.next
            head = head.next

        pre = dummy
        # second loop
        # set random pointer
        while pre.next:
            if pre.next.random:
                pre.next.random = nodeMap[pre.next.random]
            pre = pre.next

        return dummy.next

Reference