一个单链表,每一个节点除了会指向下一个节点之外,还有一个随机指针,随机的指向该链表本节点之外的另一个节点
比如 1------>2------>3------>4------nil
然后随机指针
1------>3
2------>4
3------>2
4------>1
复制逻辑
第一步 先在原始链表每一个节点后面创建一个取值跟其一样的节点让链表变成这样
1--->1'--->2--->2'--->3--->3'--->4--->4'---nil
第二步 在完成了第一步之后分析发现
比如想让1‘的随机指向的是3’(因为1随机指向3)那么在新链表中,1是node就有下面的公式
node(1).next(1‘).rand = node(1).rand(3).next(3')
利用这个公式就能让复制出的1‘的rand指针成功指向3’
第三步
解开生成的新链表
``
golang版本代码如下
type RandListNode struct {
Val int
Next *RandListNode
Rand *RandListNode
}
func CopyList(node *RandListNode) *RandListNode{
//先遍历一遍链表变成这样 1--1'--2--2'--3--3' current := node//搞一个变量是想复用node
for current != nil{
oldNext := current.Next
newNext := &RandListNode{
Val: current.Val,
Next: oldNext,
Rand: nil,
}
current.Next = newNext
current = oldNext//直接指向下一个
}
//现在开始拆解然后返回复制
current = node
for true{
current.Next.Rand = current.Rand.Next
current = current.Next.Next
if current == nil{
break
}
}
//然后开始恢复
current = node
newHead := node.Next
for true{
oldNext := current.Next
newNext := oldNext.Next
current.Next = newNext
if newNext != nil{
oldNext.Next = newNext.Next
}
if newNext == nil{
break
}
current = current.Next
}
return newHead
}
有疑问加站长微信联系(非本文作者)