138. Copy List with Random Pointer

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head
        # First，复制一个新的Node，插到旧的Node的后面
        #
        #  head -> node_a -> 新node_a -> node_b -> 新node_b -> node_c -> 新node_c -> ..>  -None
        #
        temp = head
        while temp:
            newNode = RandomListNode(temp.label)
            newNode.next = temp.next
            temp.next = newNode
            temp = newNode.next

        # Second, 处理random pointer，
        #
        # head -> node_a -> 新node_a -> node_b -> 新node_b -> node_c -> 新node_c -> ..>  -None
        #
        # 如果node的random pointer 不是None，新node.random 应该指向node.random指向的 node 的下一个，
        # 因为node的下一个是这个node的copied node
        #
        temp = head
        while temp:
            if temp.random:
                temp.next.random = temp.random.next
            temp = temp.next.next

        # Finally, 重组旧的Linked list , and extract the new nodes
        ret = RandomListNode(0)
        new_temp = ret
        temp = head
        while temp:
            new_temp.next = temp.next
            new_temp = new_temp.next
            next_old = temp.next.next
            temp.next = next_old
            temp = temp.next
        return ret.next