济南网站建设0531soso,建设企业网站下载,windows优化大师官方免费,我为群众办实事项目清单138. 复制带随机指针的链表 这个题结构体特殊#xff0c;需要更改上一篇博客的node结构体 给定一个链表#xff0c;每个节点包含一个额外增加的随机指针#xff0c;该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表…138. 复制带随机指针的链表 这个题结构体特殊需要更改上一篇博客的node结构体 给定一个链表每个节点包含一个额外增加的随机指针该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。
示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2
输入head [[1,1],[2,1]] 输出[[1,1],[2,1]] 示例 3
输入head [[3,null],[3,0],[3,null]] 输出[[3,null],[3,0],[3,null]] 示例 4
输入head [] 输出[] 解释给定的链表为空空指针因此返回 null。
提示
-10000 Node.val 10000 Node.random 为空null或指向链表中的节点。 节点数目不超过 1000 。
解法
/*** Definition for a Node.* type Node struct {* Val int* Next *Node* Random *Node* }*/
func copyRandomList(head *Node) *Node {//1-2(4)-3-4-nilif head nil {return nil}//1-1-2-2-3-3-4-4res : copyNextPoint(head)//1-1-2(4)-2(4)-3-3-4-4res copyRandomPoint(res)//1-2(4)-3-4-nilres listCut(res)return res
}func copyNextPoint(head *Node) *Node {temp : new(Node)temp.Next headp : headfor p ! nil {tmp : new(Node)tmp.Val p.Valtmp.Next p.Nextp.Next tmpp p.Next.Next}return temp.Next
}func copyRandomPoint(head *Node) *Node {temp : new(Node)temp.Next headp : headfor p ! nil {if p.Random ! nil {temp_random : p.Nexttemp_random.Random p.Random.Next}p p.Next.Next}return temp.Next
}func listCut(head *Node) *Node {temp : new(Node)res : tempfor old : head; old ! nil;{res.Next old.Nextold.Next res.Next.Nextold, res old.Next, res.Next}return temp.Next
}