【剑指offer】复杂链表的复制（python）

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路
由于本题对链表的复制增加了一个random指针指向任意一个节点，因此在对每个节点进行复制时，需要分别保存next指针指向的节点 node和next指针指向的值node_value，以及random指针指向的节点random_node和random指针指向的值random_value，分为以下两步进行复制：
1、复制random指针指向的节点：
若random指针指向的节点为当前节点之前的节点，即已创建的节点，则直接将指针指向该节点即可：

if temp2.label in node_value:
	pHead1Copy.random = node[node_value.index(temp2.label)]

若random指针指向的节点不是当前节点之前的节点，则重新创建节点，并将节点和值分别存储在random_node和random_value中。

n = RandomListNode(temp2.label)
pHead1Copy.random = n
random_node.append(n)
random_value.append(temp2.label)

2、复制next指针指向的节点：
若next指针指向的节点为random指针已经创建的节点，则直接将指针指向该节点即可：

 pHead1Copy.next = random_node[random_value.index(temp.label)]

若next指针指向的节点不是random指针已经创建的节点，则创建新节点，并将节点和值分别存储在node和node_value中。

n = RandomListNode(temp.label)
pHead1Copy.next = n
node.append(n)
node_value.append(temp.label)

完整代码

# -*- 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
        if not pHead:
            return None
        pHeadCopy = pHead
        pHead1 = RandomListNode(pHeadCopy.label)
        pHead1Copy = pHead1
        random_node = []
        random_value = []
        node = []
        node_value = []
        while pHeadCopy.next:
            temp = pHeadCopy.next
            if temp.label in random_value:
                pHead1Copy.next = random_node[random_value.index(temp.label)]
            else:
                n = RandomListNode(temp.label)
                pHead1Copy.next = n
                node.append(n)
                node_value.append(temp.label)
            temp2 = pHeadCopy.random
            if temp2:
                if temp2.label in node_value:
                    pHead1Copy.random = node[node_value.index(temp2.label)]
                else:
                    n = RandomListNode(temp2.label)
                    pHead1Copy.random = n
                    random_node.append(n)
                    random_value.append(temp2.label)
            pHead1Copy = pHead1Copy.next
            pHeadCopy = pHeadCopy.next
        return pHead1