141. Linked List Cycle

Linked List Cycle - LeetCode

• Rust非対応だったので、Rubyで解いた

考えたこと

• 確認した要素をHashとして持っておけば、O(n)で解ける
  • だが、valが重複しないとは書いてないので、怪しい
  • また、空間計算量がO(n)となるが、問題には O(1) と書いてある

解法

• ２つのポインタを使って確認することで、サイクルがあれば循環するのでいつか追いつく。
• サイクルが存在しなければ、falseを返す

初期コード

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} head
# @return {Boolean}
def hasCycle(head)
end

解法１

def hasCycle(head)
  seen = {}
  current = head

  while !current.nil?
    if seen.has_key?(current)
      return true
    else
      seen[current] = current.val
    end

    current = current.next
  end

  false
end

解法２

def hasCycle(head)
  fast = slow = head

  while fast && fast.next
    fast = fast.next.next
    slow = slow.next

    return true if fast == slow
  end

  false
end

参考

FAST & SLOW POINTER — FLOYD’S CYCLE DETECTION — TORTOISE AND HARE ALGORITHM | by Esra ŞAHİN | Medium