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

• 首先复制新节点到每个源节点的后面，即next节点。然后复制新节点的random节点，这里因为有了新节点，
  所以random节点块与题给的样式相同。最后拆分新旧节点，先设置一个新节点的头结点，然后拆分属于新节点的那个节点连续块。

一种普通方法，一种递归方法。注意递归时有两个next，一个是该节点的next指向，另一个是下一个节点的内容

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        if pHead is None:
            return None
        ptmp = pHead
        while ptmp:
            node = RandomListNode(ptmp.label)
            node.next = ptmp.next
            ptmp.next = node
            ptmp = node.next
        ptmp = pHead
        while ptmp:
            if ptmp.random:
                ptmp.next.random = ptmp.random.next
            ptmp = ptmp.next.next
        old = pHead
        new = pHead.next
        node = pHead.next
        while old:
            old.next = old.next.next
            if new.next:
                new.next = new.next.next
                new = new.next
            old = old.next
        return node

    def Clone(self, pHead):
        if pHead is None:
            return None
        newphead = RandomListNode(pHead.label)
        newphead.next = pHead.next
        newphead.random = pHead.random
        newphead.next = self.Clone(pHead.next)

        return newphead