给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。你的代码 只 接受原链表的头节点 head 作为传入参数。题目很长简单来说就是链表的节点有一个next指针和random指针next指针指向下一个节点random节点指向其他节点。首先是先复制一下链表即每个原节点后面复制一个新节点先操作next指针。然后是把复制后的节点操作一下random指针。容易发现新节点的random指向原节点random指向的next节点。最后就是拆开新链表和原链表因为题目要求需要保存原链表所以需要用两个指针。# Definition for a Node.classNode:def__init__(self,x,nextNone,randomNone):self.valint(x)self.nextnextself.randomrandomclassSolution(object):defcopyRandomList(self,head): :type head: Node :rtype: Node ifnothead:returnNonepheadwhilep:new_nodeNode(p.val)new_node.nextp.nextp.nextnew_node pnew_node.nextpheadwhilep:ifp.random:p.next.randomp.random.nextpp.next.nextdummyNode(0)copy_curdummy# 负责构建复制链表curhead# 负责遍历原链表whilecur:copy_nodecur.next# 先保存副本比如 Acur.nextcopy_node.next# 恢复原链表A - Bcopy_cur.nextcopy_node# 把副本接到复制链表dummy - Acopy_curcopy_node# 移动复制链表的指针curcur.next# 移动原链表的指针到 Breturndummy.next