《剑指offer》刷题系列——（十六）复杂链表的复制

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路

第一步，复制原始链表上的每个节N创建N’，然后把这些创建出来的节点链接起来 第二步，设置复制节点的random值，假设原始链表上的N->random指向S，则N’->random指向S->next。 第三步，将长链表拆分。

代码

class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if head == None: return None # 插入复制的val和next cur = head while cur: new_node = Node(cur.val,None,None) new_node.next = cur.next new_node.random = None cur.next = new_node cur = cur.next.next # 设置复制的random cur = head while cur: ## 设置复制节点的random cur.next.random = cur.random.next if cur.random else None cur = cur.next.next pnode1 = head pnode2 = head.next finalnode = head.next while pnode2: pnode1.next = pnode1.next.next pnode2.next = pnode2.next.next if pnode2.next else None pnode1 = pnode1.next pnode2 = pnode2.next return finalnode

复杂度

时间复杂度O(n)，空间复杂度O(1)