Java实现环形链表

实现基本的增删改查以及约瑟夫问题

package 链表;

public class CircleSingleLinkedListDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.show();
        System.out.println("=========================");

        circleSingleLinkedList.add(1);
        circleSingleLinkedList.add(4);
        circleSingleLinkedList.add(3);
        circleSingleLinkedList.add(2);
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.show();
        System.out.println("=========================");

        System.out.println(circleSingleLinkedList.delete(6));
        circleSingleLinkedList.show();
        System.out.println("=========================");

        circleSingleLinkedList.add(1);
        circleSingleLinkedList.show();
        circleSingleLinkedList.Josephus(5);
        System.out.println("=========================");


    }

}

/**
 * 链表类，包含对循环链表的增删和约瑟夫方法
 * 链表中的元素以值递增方式存入
 */
class CircleSingleLinkedList {
    //头结点，val存储当前链表元素个数
    private final CircleSingleLinkedListNode headNode = new CircleSingleLinkedListNode(0);

    /**
     * 将元素加入循环链表(val升序)
     *
     * @param val
     */
    public void add(int val) {
        CircleSingleLinkedListNode newNode = new CircleSingleLinkedListNode(val);
        if (headNode.val == 0) {    //首个元素节点和其他元素节点插入方式不同
            headNode.nextNode = newNode;
        } else {
            CircleSingleLinkedListNode temp = headNode;
            int i = 0;
            while (temp.nextNode.val < val && i < headNode.val) {
                temp = temp.nextNode;
                i++;
            }
            if (i == 0) {
                CircleSingleLinkedListNode tempRear = headNode.nextNode;
                while (tempRear.nextNode != headNode.nextNode)
                    tempRear = tempRear.nextNode;
                tempRear.nextNode = newNode;
                newNode.nextNode = headNode.nextNode;
                headNode.nextNode = newNode;
                headNode.val++;
                return;
            }
            newNode.nextNode = temp.nextNode;
            temp.nextNode = newNode;
        }
        headNode.val++;
    }

    /**
     * 打印链表所有元素
     */
    public void show() {
        if (headNode.val == 0) {
            System.out.println("链表为空");
            return;
        }
        CircleSingleLinkedListNode temp = headNode.nextNode;
        while (temp.nextNode != headNode.nextNode) {
            System.out.print(temp.val + "  ");
            temp = temp.nextNode;
        }
        System.out.println(temp.val);
    }

    /**
     * 按位置删除某元素
     *
     * @param loc 元素位置
     * @return 被删除元素的值
     */
    public int delete(int loc) {
        CircleSingleLinkedListNode temp = headNode.nextNode;
        if (loc % headNode.val == 1) {
            int val = headNode.nextNode.val;
            //头结点指向第二个元素节点，环形链表尾部也指向第二个元素节点
            //temp遍历到链表尾
            while (temp.nextNode != headNode.nextNode) {
                temp = temp.nextNode;
            }
            headNode.nextNode = headNode.nextNode.nextNode;
            temp.nextNode = temp.nextNode.nextNode;

            headNode.val--;
            return val;
        }
        for (int i = 2; i < loc; i++) {
            temp = temp.nextNode;
        }
        int val = temp.nextNode.val;
        temp.nextNode = temp.nextNode.nextNode;
        headNode.val--;
        return val;
    }

    /**
     * 约瑟夫问题
     *
     * @param num 第几个元素输出
     */
    public void Josephus(int num) {
        if (num == 1) {
            show();
            return;
        }
        CircleSingleLinkedListNode temp = headNode;
        while (headNode.val != 1) {
            //temp指向待删除节点的前一节节点
            for (int i = 0; i < num - 1; i++)
                temp = temp.nextNode;
            System.out.print(temp.nextNode.val + "  ");
            //删除目标节点
            if (temp.nextNode == headNode.nextNode) {
                temp.nextNode = temp.nextNode.nextNode;
                headNode.nextNode = headNode.nextNode.nextNode;
            } else {
                temp.nextNode = temp.nextNode.nextNode;
            }
            headNode.val--;
        }
        System.out.println(headNode.nextNode.val);
        delete(1);
    }
}

/**
 * 节点类，每一个对象就是循环链表中的一个节点
 */
class CircleSingleLinkedListNode {
    public int val;
    public CircleSingleLinkedListNode nextNode;

    public CircleSingleLinkedListNode(int val) {
        this.val = val;
        nextNode = this;
    }
}