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

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        #定义哈希表，用原链表的节点作为键，新拷贝的链表节点做为值
        Mydict = {}
        newPhead = RandomListNode(-1)
        pre = newPhead
        cur = pHead


        #拷贝旧链表
        while cur:
            clone = RandomListNode(cur.label)
            Mydict[cur] = clone
        #用尾插法将旧链表链接起来
            pre.next = clone
            pre = pre.next
            cur = cur.next
        
        #遍历哈希表，找到存在random的节点，把它的节点的值对应的拷贝的节点赋值过去
        for (key, value) in Mydict.items():
            if not key.random:
                value.random = None

            else:
                value.random = Mydict[key.random]
        return newPhead.next