高价做单网站,网站设计哪家强,济南网站优化收费标准,3d建模教程题目描述
请实现 copyRandomList 函数#xff0c;复制一个复杂链表。在复杂链表中#xff0c;每个节点除了有一个 next 指针指向下一个节点#xff0c;还有一个 random 指针指向链表中的任意节点或者 null。
题目分析
题中每个节点新增了 random 指针#xff0c;指向链表…题目描述
请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。
题目分析
题中每个节点新增了 random 指针指向链表中的 任意节点 或者 空 。这个 random 指针就意味着在复制时除了基础的结点创建 还需要创建节点中的 pre.random指针及其指向的节点 。
本题难点
在复制链表的过程中构建新链表各节点的 random 引用指向。
解题
哈希映射
可以将原节点与新节点进行哈希映射然后再查哈希表去构建每个节点的random指针。时间复杂度O(n) 空间复杂度O(n)
/*** Definition for a Node.* type Node struct {* Val int* Next *Node* Random *Node* }*/ // 哈希表映射 时间复杂度O(n) 空间复杂度O(n)
func copyRandomList(head *Node) *Node {if head nil {return head}// 新建链表并将其与原链表结点映射nodeMap : make(map[*Node]*Node, 10)var newHead *Nodevar newCur *Nodecur : headfor cur ! nil {node : new(Node)node.Val cur.ValnodeMap[cur] nodecur cur.Nextif newCur nil{newHead nodenewCur newHeadcontinue}newCur.Next nodenewCur newCur.Next}// 建立random关系cur headnewCur newHeadfor cur ! nil {newCur.Random nodeMap[cur.Random]newCur newCur.Nextcur cur.Next }return newHead
}衍生拼接
可以先遍历一遍初始链表在每个节点后衍生一个新节点在创建新链表时新节点的random指向的就是原节点random所指结点后的衍生结点。 初始链表
衍生结点 拆分还原链表
构建radom指向 拆分并还原链表 全部拆分并还原
代码实现
/*** Definition for a Node.* type Node struct {* Val int* Next *Node* Random *Node* }*/// 拼装分解
func copyRandomList(head *Node) *Node {if head nil {return head}// 拼接子节点在源节点后衍生新节点cur : headfor cur ! nil {node : new(Node)node.Val cur.ValnextNode : cur.Nextnode.Next nextNodecur.Next nodecur nextNode}// 建立新节点random指向cur headfor cur ! nil {nextNode : cur.Nextif cur.Random ! nil {nextNode.Random cur.Random.Next}cur nextNode.Next}// 将子节点从原链表中分离cur headvar newHead *Nodevar newCur *Nodefor cur ! nil {nextNode : cur.Nextcur.Next nextNode.Nextcur cur.Nextif newCur nil {newHead nextNodenewCur newHeadcontinue}newCur.Next nextNodenewCur newCur.Next}return newHead}
