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

润雨冰雪 · · 521 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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


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

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:润雨冰雪

查看原文:有随机指针的单链表的复制

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

521 次点击  
加入收藏 微博
下一篇:2020-10-17
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传