Skip to content

step2.md

Latest commit

 

History

History
123 lines (106 loc) · 3.31 KB

step2.md

File metadata and controls

123 lines (106 loc) · 3.31 KB
Raw

step2 他の方の解答を見る

yus-yus/leetcode#4

現在のノード(node)と重複していないノードを扱うためのポインタ(unique)を用意する nodeと次のノードの値が同じ間、nodeを進める uniqueとnodeを繋げることで重複するノードを全て削除することができる この発想は思いつかなかったが、それなりに自然に感じた。

prev_headよりもdummy_headの方が自分で用意したノードであることがわかるので良い。 dummy_headに入れる値はnilよりもFloat::INFINITYの方がよりあり得ない(=dummyとわかる)ので良いかもしれない。

個人的には、以下のようにif - elseではなくnextで抜けるとduplicated_value = node.valがなぜduplicateなのかがわかりづらくなる気がしている。 あれ、node.valがduplicateなのはなんでだっけ…？あ、node.val != node.next.valの条件が前にあるからここの処理はnode.val == node.next.valが保証されてるのか…という感じ。

def delete_duplicates(head)
    dummy_head = ListNode.new(Float::INFINITY, head)
    unique = dummy_head
    node = head

    while node
        if !node.next
            unique.next = node
            break
        end
        
        if node.val != node.next.val
            unique.next = node
            unique = unique.next
            node = node.next
            next
        end

        duplicated_value = node.val
        while node && node.val == duplicated_value
            node = node.next
        end
        unique.next = node
    end

    dummy_head.next
end

以下の二つどちらかが良いと考える。

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def delete_duplicates(head)
    dummy_head = ListNode.new(Float::INFINITY, head)
    unique = dummy_head
    node = head

    while node
        if !node.next
            unique.next = node
            break
        end

        if node.val == node.next.val
            duplicated_value = node.val
            while node && node.val == duplicated_value
                node = node.next
            end
            unique.next = node
        else
            unique.next = node
            unique = unique.next
            node = node.next
        end
    end

    dummy_head.next
end
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def delete_duplicates(head)
    dummy_head = ListNode.new(Float::INFINITY, head)
    unique = dummy_head
    node = head

    while node
        if !node.next
            unique.next = node
            break
        end

        if node.val == node.next.val
            duplicated_value = node.val
            while node && node.val == duplicated_value
                node = node.next
            end
            unique.next = node
            next
        end

        unique.next = node
        unique = unique.next
        node = node.next
    end

    dummy_head.next
end