题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
示例1
输入
输出
# -*- coding:utf-8 -*-# class RandomListNode:# def __init__(self, x):# self.label = x# self.next = None# self.random = Noneclass Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here #如果链表为空链表,则返回本身即可 #如果非空 需要进行复制操作,如果没有特殊指针, #只需要复制next都能很快做出来,但是加上特殊指针这就需要一定技巧, #因为特殊指针随便指,而你每次找特殊指针所指的节点都需要从头开始遍历找起, if not pHead: return pHead cloNode = pHead while cloNode: node = RandomListNode(cloNode.label) node.next = cloNode.next cloNode.next = node cloNode = node.next cloNode = pHead while cloNode: node = cloNode.next if cloNode.random: node.random = cloNode.random.next cloNode = node.next cloNode = pHead pHead = pHead.next while cloNode.next: node = cloNode.next cloNode.next = node.next cloNode = node return pHead