单向环形链表-约瑟夫问题(java)

 
/**
 * 环形链表节点
 */
public class CicleNode {
    private int no;
    private CicleNode next;
    public CicleNode(int no){
        this.no=no;
    }
 
    public int getNo() {
        return no;
    }
 
    public void setNo(int no) {
        this.no = no;
    }
 
    public CicleNode getNext() {
        return next;
    }
 
    public void setNext(CicleNode next) {
        this.next = next;
    }
 
    @Override
    public String toString() {
        return "CicleNode{" +
                "no=" + no +
                '}';
    }
}

 
 
/**
 * 单向环形链表
 */
public class CicleSingleLinkedList {
    private CicleNode first;
 
    public CicleNode getFirst() {
        return first;
    }
 
    public void addNode(int nums) {
        if (nums < 1) {
            return;
        }
        //最后一个节点
        CicleNode cur = null;
        for (int i = 1; i <= nums; i++) {
            CicleNode temp = new CicleNode(i);
            if (i == 1) {
                first = temp;
                cur = first;
                continue;
            }
            //新增一个节点
            cur.setNext(temp);
            //重新标记最后一个节点
            cur = temp;
        }
        //最后一个节点指向第一个节点
        cur.setNext(first);
    }
 
    /**
     * 约瑟夫问题
     * 从第一节点开始数数，数到第num个节点，第num个打印，并且从链表删除
     *
     * @param num
     */
    public void go(int num) {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        if (num < 1) {
            System.out.println("输入有误");
        }
        //初始化辅助元素，位于尾部，记录删除节点的前一个节点
        CicleNode tail = first;
        while (true) {
            if (tail.getNext() == first) {
                break;
            }
            tail = tail.getNext();
        }
 
        while (true) {
            //移动指针
            for (int i = 0; i < num - 1; i++) {
                tail = tail.getNext();
                first = first.getNext();
            }
            System.out.println(first);
            //重新链接环形链表
            first = first.getNext();
            tail.setNext(first);
            //链表只有一个元素
            if (first == tail) {
                System.out.println(first);
                break;
            }
        }
    }
 
    public void showLnkedList() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        CicleNode temp = first;
        while (true) {
            System.out.println(temp);
            temp = temp.getNext();
            if (temp == first) {
                break;
            }
        }
    }
}

public class CicleSingleLinkedListDeno {
    public static void main(String[] args) {
        CicleSingleLinkedList list = new CicleSingleLinkedList();
        list.addNode(5);
        list.showLnkedList();
        System.out.println("");
        list.go(2);
    }
}