138. 復(fù)制帶隨機指針的鏈表

這個題結(jié)構(gòu)體特殊，需要更改上一篇博客的node結(jié)構(gòu)體

給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。

要求返回這個鏈表的 深拷貝。

我們用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個 [val, random_index] 表示：

val：一個表示 Node.val 的整數(shù)。
random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1）；如果不指向任何節(jié)點，則為 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）或指向鏈表中的節(jié)點。
節(jié)點數(shù)目不超過 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 }

總結(jié)

以上是生活随笔為你收集整理的138. 复制带随机指针的链表 golang的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。