Copy List with Random Pointer

首先用空间的做法是和clone graph一样的，这里还可以用一种不需要额外空间的做法，主要是对链表进行三次遍历，第一次在每个结点之间加拷贝点，第二次对拷贝点的random指针赋值，第三遍把拷贝点从原链表中拿出组成新链表

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        cur = head
        while cur:
            tmp = cur.next
            childNode = RandomListNode(cur.label)
            cur.next = childNode
            childNode.next = tmp
            cur = tmp

        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next

        result = RandomListNode(10)
        tail = result
        cur = head
        while cur:
            tail.next = cur.next
            cur.next = cur.next.next
            cur = cur.next
            tail = tail.next

        return result.next