LoginSignup
0
0

More than 3 years have passed since last update.

leet code 83 Remove Duplicates from Sorted List の覚え書き

Posted at

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も変更される。

という、大きな仮説を立てました。
よくわかる解説が欲しい。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0