83 Remove Duplicates from Sorted List
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
この問題が曲者すぎた。
ぱっと見で簡単やろうと思った自分を殴りたい。激ムズでっせ。
ListNodeの値は[1,1,3]
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next //これでheadも更新済み
fmt.Println(head, "headそのもの")
fmt.Println(head.Next, "head.Next")
fmt.Println(cur.Next, "cur.Next")
} else {
cur = cur.Next
//ここでcur自身を新しく作る(上書き)ので,curはheadとは別物になる
//curという入れ物自体は変化する
//しかし、入れた値のNextは番地を与えているので、中身を変えるとheadも変わる
}
}
return head
}
ここで、考えなければならないことが大きく3つある。
ListNodeの扱い方
アルゴリズムを考える
ポインタ(番地とか)
その中でも、Listnodeとポインタが時間を取られたところ。
1 ListNode
// * Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
これはstruct(構造体)である。すでに定義済みのものを扱うとのこと
でもその中身とかどうやって見るのかわからん。調べてみた。
https://play.golang.org/p/StDSHvDEvb
&ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: &ListNode{}}}}
中身はこうなっていて、2を取得するには、ListNode.Val、4を取得するにはListNode.Next.Valと書く。
ちなみに最後のNextは{0,nil}になるみたいです。⬅︎重要!
2 ポインタ
if分のprintを実行すると以下のようになる。
&{1 0xc000086050} headそのもの
&{3 0xc000086060} head.Next
&{3 0xc000086060} cur.Next
&{1 0xc000086050} headそのもの
&{3 0xc000086070} head.Next
&{0 <nil>} cur.Next
いかなる時でもheadの番地は変化していないのがわかる。
headの入れ物自体は変化はしないが、実際にはheadの中身(Next)は変化しているのもわかる。
head = [Val:1,Next{Val:1,Next:{Val:3,Next{}}}]
headの変数の入れ物自体は変化はしていない。これ→[]
headの中身head.Nextは変化しているので番地は変更される[Val:1,Next:{Val:3,Next{}}]
elseの処理の cur = cur.Nextはcurを上書きしている(つまり新しく作成しているので番地は変更になる)
けれども、その中身のNextの番地はheadのものなのでcur.Nextをいじるとhead.Nextも変更される。
という、大きな仮説を立てました。
よくわかる解説が欲しい。