输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
Solutions
Python 作弊解法
# -*- 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
import copy
return copy.deepcopy(pHead)
拆解的方法
还是要强调一下，在链表遍历的时候，千万不要拿表头的元素去迭代。在拆分过程中也是，因为要返回新的复制结果，那么在迭代时需要两个指针结点，一个指向最原始的头结点，一个是迭代用的。
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
def CloneNodes(self, pHead):
# 复制原始链表的每个结点, 将复制的结点链接在其原始结点的后面
pNode = pHead
while pNode:
new_Node = RandomListNode(pNode.label)
new_Node.next = pNode.next
pNode.next = new_Node
new_Node.random = None
pNode = new_Node.next
def ConnectRandomNodes(self, pHead):
# 将复制后的链表中的克隆结点的random指针链接到被克隆结点random指针的后一个结点
pNode = pHead
while pNode:
if pNode.random:
pNode.next.random = pNode.random.next
pNode = pNode.next.next
def ReconnectNodes(self, pHead):
# 拆分链表：将原始链表的结点组成新的链表, 复制结点组成复制后的链表
pNode = pHead
pClonedHead = pClonedNode = pHead.next
pNode.next = pClonedNode.next
pNode = pNode.next
while pNode:
pClonedNode.next = pNode.next
pClonedNode = pClonedNode.next
pNode.next = pClonedNode.next
pNode = pNode.next
return pClonedHead
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return None
self.CloneNodes(pHead)
self.ConnectRandomNodes(pHead)
return self.ReconnectNodes(pHead)
递归方法
还可以用递归的方式来做，其实也比较直观，而且时间复杂度上更小。
# -*- 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