package com.dfsn.cloud.eureka;

public class AnnulusLinkedList<T> {

    // 頭節點
    private Node frist;

    // 元素個數
    private int size;

    public void add(T t) {
        // 添加第一個元素時，它的下一個指向它自己
        if (frist == null) {
            Node newNode = new Node(t, null);
            frist = newNode;
            newNode.next = frist;
        } else {
            Node newNode = new Node(t, null);
            Node temp = frist;
            // 如果Node.next是first說明它是最後一個節點了，在它後邊添加
            while (temp.next != frist) {
                temp = temp.next;
            }
            // 既然找到了最後一個，就將新創建的添加到最後一個的末尾
            temp.next = newNode;
            // 最後新添加Node.next指向frist
            newNode.next = frist;
        }
        size++;
    }

    // 獲取長度
    public int size() {
        return size;
    }

    // 約瑟夫環又稱丟手絹殺人遊戲
    // 從鏈表的start位置開始數countNum個位置並且刪除該位置的Node
    // 其實這個題用雙向環形鏈表的難度會低一點，只要做一個計數器 l，遞增l並且不斷地node.next
    // l==countNum後刪除該node即可具體做法如下兩行程式碼
    // node.prev.next=node.next
    // node.next.prev=node.prev
    // 然後重置l，繼續自增查詢。
    // 但是如果是單向環形鏈表就要考慮一個問題，當l==countNum時，該如何刪除這個元素？
    // 單向鏈表無法自己刪除自己，只能通過上級刪掉自己。問題是，單向鏈表又沒有prev
    // 所以這需要我們維護兩個node，一個是frist，兩一個是last,last.next就是frist。
    // 也就是當l滿足條件後，frist=frist.next;last.next=frist;
    // 然後重置l，繼續自增查詢。
    public void josehu(int start, int countNum) {
        if (size == 0) {
            throw new RuntimeException("沒有元素無法計算");
        }
        if (countNum < 1) {
            throw new RuntimeException("countNum不能小於1");
        }
        if (start < 1) {
            throw new RuntimeException("start不能小於1");
        }
        if (start > size) {
            throw new RuntimeException("start位置不能大於" + size);
        }

        // 首先找到最後一個節點，最後一個節點的條件就是它的next==frist
        Node last = this.frist;
        while (true) {
            if (last.next == this.frist) {
                break;
            } else {
                last = last.next;
            }
        }

        // 第一個節點就是frist
        Node frist = this.frist;
        // 因為要從start位置開始數數，所以要找到start
        // frist和last要同時向前移動，但last始終在frist前邊
        for (int i = 1; i < start; i++) {
            frist = frist.next;
            last = last.next;
        }

        // 計數器
        int l = 1;
        while (true) {
            // 如果==1說明就剩下一個Node就停止，最後把它自殺就行
            if (size == 1) {
                break;
            } else {
                if (l == countNum) {// 如果l==countNum表示當前frist要被殺掉
                    System.out.println(frist.item);
                    // frist的下一個成為新的frist
                    frist = frist.next;
                    // last的下一個還是frist
                    last.next = frist;
                    // 重置計數器
                    l = 1;
                    size--;
                } else {// 如果l!=countNum那麼把計數器+1，frist和last同時向後偏移
                    frist = frist.next;
                    last = last.next;
                    l++;
                }
            }
        }
        // 列印最後一個元素
        System.out.println(frist.item);
        // 置為null表示自殺
        frist = null;
        size--;
    }

    // 查看鏈表
    public void show() {
        Node temp = frist;
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp.next == frist) {
                System.out.println(temp);
                break;
            }
        }
    }

    // 節點對象
    class Node {
        private T item;
        private Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node [item=" + item + "]";
        }

    }
}

public static void main(String[] args) {
        AnnulusLinkedList<String> annulusLinkedList = new AnnulusLinkedList<>();
        annulusLinkedList.add("A");
        annulusLinkedList.add("B");
        annulusLinkedList.add("C");
        annulusLinkedList.add("D");
        annulusLinkedList.add("E");
        annulusLinkedList.add("F");
        annulusLinkedList.add("G");
        annulusLinkedList.add("H");
        annulusLinkedList.josehu(2, 2);
    }