题解 | #复杂链表的复制#

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    nodeMap = {}
    def Clone(self, pHead):
        # write code here
        #递归，去处理每一个label，同时使用一个map维护当前带有xlabel的节点是否已经处理过了
        
        if pHead == None :
            return None
        
        if pHead.label in Solution.nodeMap:
            return Solution.nodeMap[pHead.label]
        else:
            #处理当前label
            currentNode = RandomListNode(pHead.label)
            Solution.nodeMap[pHead.label] = currentNode
            
            currentNode.next = self.Clone( pHead.next)
            currentNode.random = self.Clone(pHead.random)
            return currentNode