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

# -*- coding: utf-8 -*-# @Time : 2019-07-05 15:52# @Author : Jayce Wong# @ProjectName : job# @FileName : complexListNodeClone.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJayceclass RandomListNode: def __init__(self, x): self.label = x self.next = None self.random = None""" 解法1： 直接复制链表的话，由于每个节点有一个随机指针指向任意的位置(包括空指针)，因此如果用最朴素的方法 来解决，需要在将所有节点复制完之后，对每个节点的random属性遍历一次整个链表，因此假设共有n个 节点，那么这种最朴素的解法的时间复杂度为O(n^2) 解法2： 解法1之所以效率低是因为每个节点的random指针的指向需要遍历整个链表才能找到，如果我们牺牲空间来 换时间的话，那么就可以做到时间复杂度为O(n), 额外使用空间O(n)。 具体做法可以是用一个字典来保存每个节点及其对应的克隆节点的地址，这样就可以通过查询这个哈希表在 O(1)的时间内找到random指针所指向的节点 解法3： 解法2之所以能把时间复杂度降下来，是因为保存了原始节点和对应克隆节点的位置关系，因此可以很快找到 原始节点对应的克隆节点在哪。如果我们在复制链表的时候就让克隆节点跟在原始节点后面，那么就可以在 不额外使用哈希表的情况下做到时间复杂度为O(n)了"""class Solution2: def Clone(self, pHead): if not pHead: return None nodeTable = dict() # 用于保存原始节点对应的克隆节点的地址 pClone = RandomListNode(pHead.label) # 由于节点类型无法哈希，因此用地址作为key nodeTable[id(pHead)] = pClone pNode = pHead pNode = pNode.next cloneNode = pClone # 这个循环用于将原始链表复制出来，但是先忽略random指针，关键在于要用这个字典保存 # 原始节点和对应克隆节点的地址 while pNode: cloneNode.next = RandomListNode(pNode.label) nodeTable[id(pNode)] = cloneNode.next cloneNode = cloneNode.next pNode = pNode.next # 根据字典保存的信息设置克隆链表的random指针 cloneNode = pClone while pHead: # 需要注意的是random指针可能是指向None，而我们在字典中并没有保存None的key if pHead.random: cloneNode.random = nodeTable[id(pHead.random)] pHead = pHead.next cloneNode = cloneNode.next return pCloneclass Solution3: def Clone(self, pHead): # 解法3的思路可以分为三步： # 1. 复制整个链表，这里先忽略random指针的指向，得到形如A->A'->B->B'->C->C'的复制结果 # 2. 设置克隆节点的random指针 # 3. 将链表拆分成原始链表和克隆链表 self.cloneNode(pHead) self.connectSiblingNode(pHead) return self.reconnectNode(pHead) def cloneNode(self, pHead): pNode = pHead while pNode: pClone = RandomListNode(pNode.label) pClone.next = pNode.next pNode.next = pClone pNode = pClone.next def connectSiblingNode(self, pHead): pNode = pHead while pNode: clone_head = pNode.next if pNode.random: clone_head.random = pNode.random.next pNode = clone_head.next def reconnectNode(self, pHead): if not pHead: return None new_head = pHead.next pNode = new_head """ 这里不知为什么，如果把pHead指向new_head的左边（即pHead和new_head分别指向A和A'） 然后进入循环就不能通过牛客的OJ， 但是将pHead指向new_head的右边（即pHead和new_head分别指向B和A'） 然后进入循环就可以通过。 这两种方法在本地调试的时候都是没问题的。 """ pHead.next = pNode.next pHead = pHead.next while pHead: pNode.next = pHead.next pNode = pNode.next pHead.next = pNode.next pHead = pHead.next return new_headdef main(): # 1->3 # 2->1 # 3->2 # node = RandomListNode(1) # node.next = RandomListNode(2) # node.next.next = RandomListNode(3) # node.random = node.next.next # node.next.random = node # node.next.next.random = node.next node1 = RandomListNode(1) node2 = RandomListNode(2) node3 = RandomListNode(3) node4 = RandomListNode(4) node5 = RandomListNode(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node1.random = node3 node2.random = node5 node4.random = node2 solution = Solution2() head = solution.Clone(node1) while head: if head.random: print(head.label, head.random.label) else: print(head.label, 'None') head = head.nextif __name__ == '__main__': main()