girlnote323-contains.java - Web連載「数学ガールの秘密ノート」 第323回　アルゴリズム、なかなか大変（前編）

girlnote323-contains.java

// 注意：本文に近付けるため、Javaとしては不自然な書き方になっています
// cf: https://cakes.mu/posts/33738
class Node {
    int value;
    Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public static Node asNode(int... values) {
        Node head = new Node(0, null);
        Node p = head;
        for (int i = values.length - 1; i >= 0; i--) {
            p = new Node(values[i], p);
        }
        head.next = p;
        return head;
    }

    public static void println(Node head) {
        Node p = head.next;
        while (p != head) {
            System.out.print(p.value);
            p = p.next;
            if (p != head) {
                System.out.print(" → ");
            }
        }
        System.out.println();
    }

    // List 10
    public static boolean contains1(Node C, int v) {
        Node p = C.next;
        while (p != C) {
            if (p.value == v) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    // List 11
    public static boolean contains2(Node C, int v) {
        C.value = v;
        Node p = C.next;
        while (p.value != v) {
            p = p.next;
        }
        if (p == C) {
            return false;
        } else {
            return true;
        }
    }

    public static void main(String[] args) {
        Node C = asNode(31, 41, 59, 26, 53);
        println(C);
        System.out.println("Does <31, 41, 59, 26, 53> contain 59? => " + contains1(C, 59));
        System.out.println("Does <31, 41, 59, 26, 53> contain 99? => " + contains1(C, 99));
        System.out.println("Does <31, 41, 59, 26, 53> contain 59? => " + contains2(C, 59));
        System.out.println("Does <31, 41, 59, 26, 53> contain 99? => " + contains2(C, 99));
    }
}

$ java girlnote323-contains.java
31 → 41 → 59 → 26 → 53
Does <31, 41, 59, 26, 53> contain 59? => true
Does <31, 41, 59, 26, 53> contain 99? => false
Does <31, 41, 59, 26, 53> contain 59? => true
Does <31, 41, 59, 26, 53> contain 99? => false

https://twitter.com/hyuki/status/1393201193099292675