public class CircleSinglyLinkList {

    private Node head;

    CircleSinglyLinkList(){

        this.head = null;

    }

    CircleSinglyLinkList(Node head){

        this.head = head;

    }

    //向表头插入一个值为x的结点

    public void insertHead(int x){

        Node newNode = new Node(x);

        if(this.head == null){

            this.head = newNode;

            newNode.next = this.head;

        }else{

            Node last = this.head;

            newNode.next = this.head;

            this.head = newNode;

            while(last.next != newNode.next){

                last = last.next;

            }

            last.next = this.head;

        }

    }

    //向表尾插入一个值为x的结点

    public void insertTail(int x){

        Node newNode = new Node(x);

        if(head == null){

            this.head = newNode;

            newNode.next = this.head;

        }

        else {

            Node cur = this.head;

            while(cur.next != this.head){

                cur = cur.next;

            }

            newNode.next = this.head;

            cur.next = newNode;

        }

    }

    public void deleteData(int data){

        Node cur = findNode(data);

        Node last = this.head;

        if(cur == null){

            return;

        }

        if(cur == this.head){

            while(last.next != this.head){

                last = last.next;

            }

            this.head = cur.next;

            last.next = this.head;

            cur = null;

            return ;

        }

        Node pre = head;

        while(pre.next != cur){

            pre = pre.next;

        }

        pre.next = pre.next.next;

        cur = null;

    }

    public Node findNode(int data){

        if(head == null){

            System.out.println("链表为空");

            return null;

        }

        Node cur = head;

        while (cur.next != head && cur.value != data){

            cur = cur.next;

        }

        return cur;

    }

    @Override

    public String toString() {

        Node cur = head;

        String str = "";

        StringBuilder newStr = new StringBuilder("");

        while(cur.next != head){

            newStr.append(cur.value+"--->");

            cur = cur.next;

        }

        newStr.append(cur.value+"--->头");

        return newStr.toString();

    }

    public static void main(String[] args) {

        CircleSinglyLinkList circleSinglyLinkedList= new CircleSinglyLinkList();

//        Josephus

        int peopleNum = 10;

        int each = 3;

        int count = 1;

        for (int i = 0; i < peopleNum; i++) {

            circleSinglyLinkedList.insertTail(i+1);

        }

//        System.out.println(circleSinglyLinkedList.toString());

        Node another = circleSinglyLinkedList.head;

        Node pre = another;

        while(true){

            if(another.next == another){

                break;

            }

            if(count%3 == 0){

                pre = another.next;

                circleSinglyLinkedList.deleteData(another.value);

                count++;

                another = pre;

                System.out.println(circleSinglyLinkedList.toString());

            }else{

                another = another.next;

                count++;

            }

        }

////        circleSinglyLinkedList.deleteData(0);

//        circleSinglyLinkedList.deleteData(1);

//        circleSinglyLinkedList.insertHead(1);

////        circleSinglyLinkedList.deleteData(1);

//        circleSinglyLinkedList.insertTail(2);

////        System.out.println(circleSinglyLinkedList.findNode(1).value);

////        circleSinglyLinkedList.deleteData(1);

////        circleSinglyLinkedList.deleteData(90);

//        circleSinglyLinkedList.deleteData(1);

//        System.out.println(circleSinglyLinkedList.toString());

    }

}