leetcode算法题--复杂链表的复制

原题链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/description/?envType=study-plan-v2&envId=coding-interviews

感觉一开始想到的办法还是比较笨

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/func copyRandomList(head *Node) *Node {if head == nil {return nil}res := &Node{}p1 := headp2 := resmp1 := make(map[*Node]int)mp22 := make(map[int]*Node)idx := 0for p1!= nil {p2.Val = p1.Valif p1.Next != nil {p2.Next = &Node{}}mp1[p1] = idxmp22[idx] = p2idx++p1 = p1.Nextp2 = p2.Next}p1 = headp2 = resfor p1 != nil {if p1.Random != nil {if idx, ok := mp1[p1.Random]; ok{p2.Random = mp22[idx] } }p1 = p1.Nextp2 = p2.Next}return res
}

用回溯方法做

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/var cache = make(map[*Node]*Node)func copyRandomList(head *Node) *Node {return deepCopy(head)
}func deepCopy(head *Node) *Node {if head == nil {return nil}if node, ok := cache[head]; ok {return node }newNode := &Node{}newNode.Val = head.Valcache[head] = newNodenewNode.Next = deepCopy(head.Next)newNode.Random = deepCopy(head.Random)return newNode 
}

节点拆分法

/*** Definition for a Node.* type Node struct {*     Val int*     Next *Node*     Random *Node* }*/func copyRandomList(head *Node) *Node {if head == nil {return nil}for node := head; node != nil; node = node.Next.Next {newNode := &Node{Val: node.Val, Next: node.Next,}node.Next = newNode }for node := head; node != nil; node = node.Next.Next {if node.Random != nil {newNode := node.NextnewNode.Random = node.Random.Next }}res := head.Nextfor node := head; node != nil; node = node.Next {newNode := node.Nextnext := newNode.Nextnode.Next = nextif next != nil {newNext := next.NextnewNode.Next = newNext}}return res
}