面试题35：复杂链表的复制

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

解题思路：
本次主要是实现剑指offer的解题思路，将复杂的问题分步解决，分别为复制节点，赋值任意指针以及拆分长链表，具体如下：

35 复杂链表的赋值.png

代码实现：

# -*- 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
        '''
        python 作弊法
        import copy
        return copy.deepcopy(pHead)
        '''
        #剑指offer的解法-分布解决
        self.CopyNode(pHead)
        self.ConnectRandom(pHead)
        return self.Reconnect(pHead)

        
    #复制节点
    def CopyNode(self,pHead):
        node = pHead
        while node != None:
            cloneNode = RandomListNode(0)  #初始化
            cloneNode.label = node.label
            cloneNode.next = node.next

            node.next = cloneNode    #连接克隆节点
            node = cloneNode.next    #更新变量 
        

    #连接random指针
    def ConnectRandom(self,pHead):
        node = pHead
        while node != None:
            cloneNode = node.next
            if node.random != None:
                cloneNode.random = node.random.next

            node = cloneNode.next


    #拆分链表
    def Reconnect(self,pHead):
        node = pHead
        cloneNode = None
        CloneHead = None

        #确定克隆的头节点
        if node != None:
            CloneHead = cloneNode = node.next

            #更新变量
            node.next = cloneNode.next
            node = node.next

        #开始拆分
        while node != None:
            cloneNode.next = node.next  #上一clone节点的next
            cloneNode = node.next

            node.next = cloneNode.next  #确定node的下一节点
            node = node.next

        return CloneHead

提交结果：

附加：递归方法：
思想简单，也可以将结果正确得出！！
代码如下：

# -*- 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  pHead==None:
            return None
        newNode=RandomListNode(pHead.label)
        newNode.random=pHead.random
        newNode.next=self.Clone(pHead.next)
        return newNode