关于golang:有随机指针的单链表的复制

一个单链表，每一个节点除了会指向下一个节点之外，还有一个随机指针，随机的指向该链表本节点之外的另一个节点

比方 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
}