在 leetcode 上做到了一道題，讓回傳一個鏈表的深拷貝，感覺很有意思，記錄一下，
深拷貝和淺拷貝
什么是淺拷貝？當你在拷貝一種資料結構的時候（結構體、類、map...），如果拷貝的只是這個資料結構的參考，那么這就是淺拷貝
舉個例子（淺拷貝)
此時有一個 map，暫且命名為 "s"，存放一個 1
s := make(map[int]int, 0)
s[1] = 1
將 "s" 拷貝給 map "p"，修改 p 的值
p[1] = 2
分別列印出修改前和修改后 "s" 里存的值，看看是什么效果，
s := make(map[int]int, 0)
s[1] = 1
fmt.Println(s)
p := s
p[1] = 2
fmt.Println(s)
輸出
map[1:1]
map[1:2]
修改 p 的值，但是 s 里的值也發生了變化，這說明 s 和 p 實際上都是指向的同一塊記憶體地址，也就是說，在拷貝 s 到 p 的時候，其實只是拷貝了一個指標，這就是淺拷貝，
深拷貝
和淺拷貝與之相對應的就是深拷貝，深拷貝就不是只拷貝一個指標，而是要拷貝指標指向的記憶體中的所有資料，對于 map 的拷貝，流行的做法都是通過序列化和反序列化來做，
看題
來看一下這道題目
給定一個鏈表，每個節點包含一個額外增加的隨機指標，該指標可以指向鏈表中的任何節點或空節點，
要求回傳這個鏈表的?深拷貝，?
我們用一個由?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]]
思考
- 拷貝一個鏈表，如果沒有 random 指標，那就簡單了，就是最基礎的遍歷一次鏈表，然后創建節點值就行，
- 如果不要求深拷貝，可以在創建鏈表的時候把原鏈表的 random 指標直接賦給新鏈表，
偏偏是兩個要求都有，這就有點傷腦了，主要是要想辦法保存每一個節點的 random 指標指向的位置，在創建新鏈表的時候，相對應的指標也要指向相對的位置，
我在這里只記錄一種解法：將每個節點的克隆鏈接到對應節點的后面，使得新舊鏈表交替連接，處理 random 指標之后再把兩個鏈表分開，
鏈接之后應當是這樣，
處理 random 指標，
此時 random 已經指向了正確的位置，只需要將兩個鏈表分開就行，
golang 完整實作
func copyRandomList(head *Node) *Node {
if head == nil {
return head
}
// 復制節點，緊挨到到后面
// 1->2->3 ==> 1->1'->2->2'->3->3'
cur := head
for cur != nil {
clone := &Node{Val: cur.Val, Next: cur.Next}
temp := cur.Next
cur.Next = clone
cur = temp
}
// 處理random指標
cur = head
for cur != nil {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
cur = cur.Next.Next
}
// 分離兩個鏈表
cur = head
cloneHead := cur.Next
for cur != nil && cur.Next != nil {
temp := cur.Next
cur.Next = cur.Next.Next
cur = temp
}
// 原始鏈表頭：head 1->2->3
// 克隆的鏈表頭：cloneHead 1'->2'->3'
return cloneHead
}
公眾號：沒有夢想的阿巧 后臺回復 "群聊"，一起學習，一起進步
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/167655.html
標籤：其他
下一篇：冒泡、選擇、插入排序