一、要求

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。值得注意的是，像节点D的randomnext就是None，不是所有节点都有randomnext的非空节点

二、思路及代码

三步走

step1：在原节点后插入新建节点，注意不能用=来新建节点

step2：对新节点完善randomnext属性

step3：根据跳一跳，拆分成两个链表

class RandomListNode:def __init__(self, x):self.val = xself.next = Noneself.randomnext = Nonedef solution(headnode):if not headnode:returnCloneNodes(headnode)ConnectRandomNext(headnode)return SplitNodes(headnode)#一定要return新链表的头结点def CloneNodes(headnode):pnode=headnodewhile pnode:qnode=RandomListNode(pnode.val)qnode.next=pnode.nextpnode.next=qnodepnode=qnode.nextdef ConnectRandomNext(headnode):pnode=headnodewhile pnode:qnode = pnode.nextif pnode.randomnext:qnode.randomnext=pnode.randomnext.nextpnode=qnode.nextdef SplitNodes(headnode):pnode=headnodeqnode=cloneheadnode=headnode.nextwhile pnode:pnode.next=qnode.nextif qnode.next:qnode.next=qnode.next.next#注意最后一个节点pnode=pnode.nextqnode=qnode.nextreturn cloneheadnodenode1 = RandomListNode(1)
node2 = RandomListNode(3)
node3 = RandomListNode(5)
node1.next = node2
node2.next = node3
node1.randomnext = node3newnode=solution(node1)
print(newnode.val,newnode.next.val,newnode.randomnext.val)

三、运行结果

1 3 5

四、思考与总结

1.这个题目知道套路三步走后好像难度还行？就是不断在拆建链接

2.pq大法好