2022/04/15

Leetcode Note: Go - Remove Duplicates From Sorted List

Remove Duplicates from Sorted List - LeetCode
https://leetcode.com/problems/remove-duplicates-from-sorted-list/

  • Go 言語で取り組んだメモ

所感

  • sorted という前提があるので、ループを回して前要素と同じなら削除という実装をするれば、実現できそう
  • と思ったが配列じゃなくて linked list なので、サクッと実装は難しそう
    • 前要素をどうやって判定する？
    • 削除をどうやって実装する？

実装準備

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    return head
}

回答

Go simple solution with recursion - 0 ms - LeetCode Discuss
https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/1356619/Go-simple-solution-with-recursion-0-ms

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	} else if head.Val == head.Next.Val {
		head = deleteDuplicates(head.Next)
		return head
	} else {
		head.Next = deleteDuplicates(head.Next)
		return head
	}
}
  • シンプル
  • 前要素との比較を思いついたので、それに考えが縛られてしまった
    • まず ListNode がどのようなデータを持っているかを確認
    • Val と Next があるので、 Next.Val で次要素を参照することはできる
    • 現要素と次要素が同じか判定
      • 同じなら再帰呼び出し
        • head = deleteDuplicates(head.Next)
      • 違うなら削除
        • head.Next = deleteDuplicates(head.Next)
        • 削除は上記のように head.Next に代入することで、重複要素をスキップして実質削除が実装できる
  • 問題文は読めたが、与えられているコードをちゃんと読めていないのが敗因
    • ちゃんとコードも読もう

See Also