题目要求:

思路:

思路1：引入dict
思路1：双指针

代码如下:

思路1代码：

# -*- 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):
        mHead = p = RandomListNode(0) # 先额外定义新的链表头
        node_map = {} # 定义旧：新节点映射表
        while pHead: #遍历旧列表
            p.next = RandomListNode(pHead.label) #复制为新节点
            p = p.next
            node_map[pHead]=p # 保存旧：新节点映射关系
            pHead=pHead.next 
        for old_node,new_node in node_map.items(): # 保存旧：新节点映射关系
            if old_node.random==None: 
                new_node.random=None
            else: # 看旧节点的random，如果为空，则新节点也为空，如果不为空，就找到旧节点random对应的新节点，添加映射即可
                new_node.random=node_map[old_node.random]
        return mHead.next
        # write code here

代码如下:

思路2代码：

# -*- 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):
        if not pHead: # 为None 直接返回即可
            return pHead
        p1 = p2 = pHead
        while p1: # 先在原有链表进行复制，将复制的节点挂到原列表上
            new_node = RandomListNode(p1.label)
            new_node.next = p1.next
            p1.next = new_node
            p1 = p1.next.next
        while p2 and p2.next: # 遍历原列表节点，将新节点的random指针进行重建
            if p2.random: # 原节点random存在，则新节点p2.next.random值就为原节点random值的下一个即p2.random.next
                p2.next.random = p2.random.next
            else:
                p2.next.random = None
            p2 = p2.next.next
        p3, p4, Head = pHead, pHead.next, pHead.next
   		while p4:  # p3，p4 分别指向旧新节点
            p3.next = p3.next.next #重建旧节点指向
            if p4.next: # 若p4.next不为None，则重建新节点下一节点指向
                p4.next = p4.next.next
            p3 = p3.next #分别移动新旧节点指针
            p4 = p4.next
        # write code here