// 第 10 周 – 只有一个 End(last)指针的循环单链表
// 运行：java CircularList.java
public class CircularList {

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

    Node last; // 最后一个结点；第一个结点：last.next。空链表：null。

    // 在表尾插入 – O(1)
    void insertLast(int x) {
        Node n = new Node(x);
        if (last == null) {
            n.next = n;          // 只有一个结点的环：指向自己
        } else {
            n.next = last.next;  // 新结点指向第一个结点
            last.next = n;
        }
        last = n;
    }

    // 在表头插入 – O(1)：接在 last 之后，但 last 不动，
    // 所以新结点成为第一个结点（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;
        }
    }

    // 遍历：从第一个结点开始，直到回到起点（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("] (and back to the beginning)").toString();
    }

    // 约瑟夫问题：每数到第 k 个结点就从环中删除
    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;           // 把它从环中摘下
        }
        System.out.print("order of elimination: " + 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(" -> survivor: " + j.josephus(3));
    }
}