// 10. hét – Ciklikus (körkörös) egyirányú lista egyetlen Vég mutatóval
// Futtatás: java CircularList.java
public class CircularList {

    static class Node {
        int value;
        Node next;
        Node(int v) { value = v; }
    }

    Node last; // az utolsó elem; az első: last.next. Üres lista: null.

    // Beszúrás a végére – O(1)
    void insertLast(int x) {
        Node n = new Node(x);
        if (last == null) {
            n.next = n;          // egyelemű kör: önmagára mutat
        } else {
            n.next = last.next;  // az új elem az elsőre mutat
            last.next = n;
        }
        last = n;
    }

    // Beszúrás az elejére – O(1): a last mögé fűzzük, de a last NEM lép tovább,
    // így az új elem lesz az első (last.next)
    void insertFirst(int x) {
        Node n = new Node(x);
        if (last == null) {
            n.next = n;
            last = n;
        } else {
            n.next = last.next;
            last.next = n;
        }
    }

    // Bejárás: az elsőtől indulva, amíg vissza nem érünk (do-while!)
    String str() {
        if (last == null) return "[]";
        StringBuilder sb = new StringBuilder("[");
        Node p = last.next;
        do {
            sb.append(p.value).append(p != last ? " " : "");
            p = p.next;
        } while (p != last.next);
        return sb.append("] (és vissza az elejére)").toString();
    }

    // Josephus: minden k-adik elem kiesik a körből
    int josephus(int k) {
        Node prev = last;
        StringBuilder order = new StringBuilder();
        while (prev.next != prev) {
            for (int i = 1; i < k; i++) prev = prev.next;
            Node out = prev.next;
            order.append(out.value).append(' ');
            prev.next = out.next;           // kifűzzük a körből
        }
        System.out.print("kiesési sorrend: " + order);
        last = prev;
        return prev.value;
    }

    public static void main(String[] args) {
        CircularList c = new CircularList();
        for (int i = 1; i <= 7; i++) c.insertLast(i);
        System.out.println(c.str());
        c.insertFirst(0);
        System.out.println("insertFirst(0): " + c.str());

        CircularList j = new CircularList();
        for (int i = 1; i <= 7; i++) j.insertLast(i);
        System.out.println(" -> túlélő: " + j.josephus(3));
    }
}