1.问题描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点或者None），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
2.思路解析
如果用哈希表存储pnode和pClonenode的映射关系，需要辅助空间O(n)。采用以下方法不需要额外空间，时间复杂度还相同。
此法分三步：
（1）复制结点
（2）复制特殊指针
（3）拆分链表
3.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 if pHead==None: return None p = pHead while p!=None: pClone = RandomListNode(p.label) pClone.next = p.next p.next = pClone p = pClone.next p = pHead while p!=None: pClone = p.next pClone.random = p.random.next if p.random!=None else None p = p.next.next pCloneHead = pHead.next p = pHead pClone = pCloneHead while pClone.next!=None: p.next = pClone.next p = pClone.next pClone.next = p.next pClone = p.next p.next = None return pCloneHead