LeetCode 138. 随机链表的复制 — Go 实现节点定义typeNodestruct{ValintNext*Node Random*Node}解法一哈希表 两趟遍历推荐第一趟建立 原节点 - 新节点 的映射第二趟连接 Next 和 Random。funccopyRandomList(head*Node)*Node{ifheadnil{returnnil}// 原节点 - 新节点m:make(map[*Node]*Node)// 第一趟只拷贝值建立映射forcur:head;cur!nil;curcur.Next{m[cur]Node{Val:cur.Val}}// 第二趟连接 Next 和 Randomforcur:head;cur!nil;curcur.Next{ifcur.Next!nil{m[cur].Nextm[cur.Next]}ifcur.Random!nil{m[cur].Randomm[cur.Random]}}returnm[head]}要点· map[*Node]*Node 用原节点指针作为 key天然唯一。· 先建映射再连指针避免 Random 指向尚未创建的节点。复杂度 时间 O(n)空间 O(n)。解法二交错法O(1) 额外空间把新节点插在原节点后面A - A’ - B - B’ - …然后修 Random最后拆开。funccopyRandomList(head*Node)*Node{ifheadnil{returnnil}// 1. 在每个原节点后面插入拷贝节点forcur:head;cur!nil;{next:cur.Next cur.NextNode{Val:cur.Val,Next:next}curnext}// 2. 设置拷贝节点的 Randomforcur:head;cur!nil;curcur.Next.Next{ifcur.Random!nil{cur.Next.Randomcur.Random.Next}}// 3. 拆分原链表和拷贝链表dummy:Node{}copyCur:dummyforcur:head;cur!nil;{next:cur.Next.Next copyCur.Nextcur.Next copyCurcopyCur.Next cur.Nextnext curnext}returndummy.Next}要点· cur.Next 是拷贝节点cur.Next.Next 是下一个原节点。· cur.Random.Next 正好是 cur.Random 对应的拷贝节点。· 最后拆分时必须恢复原链表的 Next否则会破坏输入。复杂度 时间 O(n)空间 O(1)。测试示例funcmain(){n1:Node{Val:7}n2:Node{Val:13}n3:Node{Val:11}n1.Nextn2 n2.Nextn3 n1.Randomniln2.Randomn1 n3.Randomn2copy:copyRandomList(n1)// 验证值fmt.Println(copy.Val)// 7fmt.Println(copy.Next.Val)// 13fmt.Println(copy.Next.Next.Val)// 11// 验证 Random 指向拷贝链表中的节点而非原节点fmt.Println(copy.Next.Randomcopy)// truefmt.Println(copy.Next.Next.Randomcopy.Next)// true}两种解法都可通过面试中写哈希表版最稳如果要求 O(1) 空间再写交错法。