LeetCoding Challenge Oct. 27: Linked List Cycle II

LeetCode October Challenge の 27 日目。

今日の問題は Linked List Cycle II。

問題の概要

• 与えられた連結リストにおいて、有向グラフで言うところの閉路が存在するかどうかを検出して存在する場合はその閉路の開始点となるノードを求める

考え方

• グラフの閉路を求める問題みたいなのは、LeetCode の何かの問題で見た気がするぞ… 🤨
  • そのときは「へえ！ こんな解法があるんだ 😲」と驚いた覚えがあるのだが、具体的なアルゴリズムはどうやら忘れてしまったようだ 😇
• ちょっと思い出せそうにないので、ナイーブなアルゴリズムで解いてみよう
  • 一度訪れたノードを HashSet に放り込んでいき、同じノードを訪れたときにそれを検出できるようにする
• 実装 → submit → accept 👍
  • Runtime: 3ms で Your runtime beats 22.99 % of java submissions. でござる 😭
• やはり、グラフ閉路の検出的なアルゴリズムを思い出すべきなようだ
  • あ、たしか、二倍速で進むポインタと等速で進むポインタの二つを使う アルゴリズムだった気がする
  • グラフに閉路があれば、二倍速で進むポインタがいつか等速で進むポインタに追いつくはず
• これで閉路があるかどうかの検出はできるようになったが、さて閉路開始点のノードを明らかにするにはどうしたらいいのかな？
  • そもそもこのアルゴリズムの名前はなんだっけ？ → fast slow pointer でぐぐってみよう → ああなるほど、Floyd's algorithm というのか
• Python のサンプルコードをお手本に実装 → submit → accept 💪
  • Runtime 0ms 達成 🎉

コード

HashSet を使うナイーブな実装

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        Set<ListNode> set = new HashSet<>();
        ListNode node = head;

        while (node != null) {
            if (!set.add(node)) {
                return node;
            }
            node = node.next;
        }

        return null;
    }
}

Floyd's algorithm による実装

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head.next.next;
        ListNode slow = head.next;

        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return null;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}