35. 复杂链表的复制

• 要特别注意链表的连接，也就是各种next的顺序，否则会造成崩溃
• 分三步进行：复制的链表clone每一个node接到dummy的相应node后面；clone的random和原node的random指向一样；把链表拆开

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        #step1 N' to N next
        dummy = pHead
        while dummy:
            clone = RandomListNode(dummy.label)
            clone.next = dummy.next
            dummy.next = clone
            dummy = dummy.next.next
        #step2, random' to random'
        dummy = pHead
        while dummy:
            clone = dummy.next
            if dummy.random:
                clone.random = dummy.random.next
            dummy = dummy.next.next
        #step3 split linked list
        dummy = pHead
        copyHead = pHead.next
        while dummy:
            copyNode = dummy.next            
            dummynext = copyNode.next            
            dummy.next = dummynext #之前没有加这句，链表断掉          
            if dummynext:                
                copyNode.next = dummynext.next            
            else:                
                copyNode.next = None            
            dummy = dummynext         
        return copyHead