有随机指针的单链表的复制

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

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

有疑问加站长微信联系