Java单向循环链表&解决约瑟夫环问题

单向循环链表

解决约瑟夫环问题

1.构造方法 及字段

public CircleLinkedList() {
    }
    /**
     * 链表的第一个节点
     */
    private Node first;

2.获取有效节点数

/**
 * 获取节点数
 */
public int elementsCount() {
    int result = 0;
    for (Node currentNode = this.first; ; currentNode = currentNode.next) {
        result++;
        if (currentNode.next == this.first)
            break;
    }
    return result;
}

3.判断循环链表是否为空

/**
 * 约瑟夫是否为空
 *
 * @return 是否为空
 */
public boolean isEmpty() {
    return this.first == null;
}

4.获取倒数第一个节点和倒数第二个节点

 /**
     * 获取倒数第二个节点
     *
     * @return
     */
    public Node getBeforeNode(int offset) {
        Node currentNode = first;
        while (currentNode.next != this.getIndexNode(offset)) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }

    /**
     * 获取最后一个节点
     */
    public Node getLastNode() {
        Node currentNode = first;
        while (currentNode.next != first) {
            currentNode = currentNode.next;
        }
        //for(currentNode=this.first;currentNode.next!=this.first;currentNode=currentNode.next);
        return currentNode;
    }

5.添加新节点

/**
 * 添加新节点
 */
public void add(String item) {
    if (isEmpty()) {
        first = new Node(item);
        first.next = first;
        return;
    }
    Node node = new Node(item, this.first);
    Node lastNode = getLastNode();
    lastNode.next = node;


}

6.根据位置获取节点

/**
 * 根据位置去获取相应的节点
 */
public Node getIndexNode(int index) {
    if (index < 0 || index >= elementsCount())
        throw new IndexOutOfBoundsException("偏移量非法：" + index);
    Node result = this.first;
    for (int i = 0; i < index; i++) {
        result = result.next;
    }

    return result;
}

7.根据起始偏移量beginNo和间隔gap实现约瑟夫环的循环输出节点内容到字符串

/**
 * 所有元素出圈
 * @param beginNo 起始偏移量
 * @param gap 间隔
 * @return 结果
 */
public String[] getAll(int beginNo, int gap){
    /*
    参数校验和出圈的准备
     */
    if(this.first == null)
        System.out.println("链表为空无法完成出列。");
    int currentElementsCount = this.elementsCount();
    if(beginNo < 1 || beginNo > currentElementsCount)
        throw new IndexOutOfBoundsException("起始位置输入有误：" + beginNo);
    /*
    使用temp指向当前链表中最后一个节点
     */
    Node temp = this.getLastNode();
    /*
    使得first和temp移动beginNo - 1次
     */
    for(int i = 0; i < beginNo - 1; i ++){
        this.first = this.first.next;
        temp = temp.next;
    }

    //实例化这个数组，将用于存放依次出圈的节点值。
    String[] result = new String[currentElementsCount];
    int resultArrayIndex = 0;
    /*
    开始进行循环出圈
     */
    while (true) {
        //经过不断的元素出圈最终会使得helper和first指向了同一个节点。
        if(temp == this.first)
            break;
        //进行移动
        for (int i = 0; i < gap - 1; i ++){
            this.first = this.first.next;
            temp = temp.next;
        }
        //将被出圈的元素值存储到数组中。
        result[resultArrayIndex ++] = this.first.item;
        this.first = this.first.next;
        temp.next = this.first;
    }
    result[resultArrayIndex ++] = this.first.item;
    return result;
}

8.重写toString 方法，实现打印单向循环链表中的元素

 @Override
    public String toString() {
        if (isEmpty())
            return "[]";
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[--");

        for (Node currentNode = this.first; ; currentNode = currentNode.next) {
            stringBuilder.append(currentNode.item);
            if (currentNode.next == this.first) {
                stringBuilder.append("--]");
                break;
            }
            stringBuilder.append(",");
        }
        return stringBuilder.toString();
    }

9.静态的节点内部类

/**
 * 节点类
 * 类似静态成员方法,可以通过类去调用
 */
public static class Node {
    public Node() {
    }

    public Node(String item) {
        this.item = item;
    }

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

    /**
     * 节点存储值
     */
    private String item;

    /**
     * 后置节点
     */
    private Node next;

    /**
     * 获取节点内容
     */
    public String getItem() {
        return item;
    }
}

10.总体实现

package com.circle.util;

import java.util.Arrays;

public class CircleLinkedList {

    public CircleLinkedList() {
    }
    /**
     * 链表的第一个节点
     */
    private Node first;

    /**
     * 获取节点数
     */
    public int elementsCount() {
        int result = 0;
        for (Node currentNode = this.first; ; currentNode = currentNode.next) {
            result++;
            if (currentNode.next == this.first)
                break;
        }
        return result;
    }

    /**
     * 约瑟夫是否为空
     *
     * @return 是否为空
     */
    public boolean isEmpty() {
        return this.first == null;
    }

    /**
     * 获取倒数第二个节点
     *
     * @return
     */
    public Node getBeforeNode(int offset) {
        Node currentNode = first;
        while (currentNode.next != this.getIndexNode(offset)) {
            currentNode = currentNode.next;
        }
        return currentNode;
    }

    /**
     * 获取最后一个节点
     */
    public Node getLastNode() {
        Node currentNode = first;
        while (currentNode.next != first) {
            currentNode = currentNode.next;
        }
        //for(currentNode=this.first;currentNode.next!=this.first;currentNode=currentNode.next);
        return currentNode;
    }

    /**
     * 添加新节点
     */
    public void add(String item) {
        if (isEmpty()) {
            first = new Node(item);
            first.next = first;
            return;
        }
        Node node = new Node(item, this.first);
        Node lastNode = getLastNode();
        lastNode.next = node;


    }

    /**
     * 根据位置去获取相应的节点
     */
    public Node getIndexNode(int index) {
        if (index < 0 || index >= elementsCount())
            throw new IndexOutOfBoundsException("偏移量非法：" + index);
        Node result = this.first;
        for (int i = 0; i < index; i++) {
            result = result.next;
        }

        return result;
    }

    /**
     * 所有元素出圈
     * @param beginNo 起始偏移量
     * @param gap 间隔
     * @return 结果
     */
    public String[] getAll(int beginNo, int gap){
        /*
        参数校验和出圈的准备
         */
        if(this.first == null)
            System.out.println("链表为空无法完成出列。");
        int currentElementsCount = this.elementsCount();
        if(beginNo < 1 || beginNo > currentElementsCount)
            throw new IndexOutOfBoundsException("起始位置输入有误：" + beginNo);
        /*
        使用temp指向当前链表中最后一个节点
         */
        Node temp = this.getLastNode();
        /*
        使得first和temp移动beginNo - 1次
         */
        for(int i = 0; i < beginNo - 1; i ++){
            this.first = this.first.next;
            temp = temp.next;
        }

        //实例化这个数组，将用于存放依次出圈的节点值。
        String[] result = new String[currentElementsCount];
        int resultArrayIndex = 0;
        /*
        开始进行循环出圈
         */
        while (true) {
            //经过不断的元素出圈最终会使得helper和first指向了同一个节点。
            if(temp == this.first)
                break;
            //进行移动
            for (int i = 0; i < gap - 1; i ++){
                this.first = this.first.next;
                temp = temp.next;
            }
            //将被出圈的元素值存储到数组中。
            result[resultArrayIndex ++] = this.first.item;
            this.first = this.first.next;
            temp.next = this.first;
        }
        result[resultArrayIndex ++] = this.first.item;
        return result;
    }

    /**
     * 打印输出
     */
    public void print() {
        if (isEmpty())
            System.out.println("空");
        Node cntNode = this.first;
        while (cntNode.next != first) {
            System.out.println(cntNode.item);
            cntNode = cntNode.next;
        }
        System.out.println(cntNode.item);
    }

    @Override
    public String toString() {
        if (isEmpty())
            return "[]";
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[--");

        for (Node currentNode = this.first; ; currentNode = currentNode.next) {
            stringBuilder.append(currentNode.item);
            if (currentNode.next == this.first) {
                stringBuilder.append("--]");
                break;
            }
            stringBuilder.append(",");
        }
        return stringBuilder.toString();
    }


    /**
     * 节点类
     * 类似静态成员方法,可以通过类去调用
     */
    public static class Node {
        public Node() {
        }

        public Node(String item) {
            this.item = item;
        }

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

        /**
         * 节点存储值
         */
        private String item;

        /**
         * 后置节点
         */
        private Node next;

        /**
         * 获取节点内容
         */
        public String getItem() {
            return item;
        }
    }
}

11.测试类

package com.circle.test;

import com.circle.util.CircleLinkedList;

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.add("宫本1");
        circleLinkedList.add("宫本2");
        circleLinkedList.add("宫本3");
        circleLinkedList.add("宫本4");
        System.out.println("-------------");

        String[] strings = circleLinkedList.getAll(1,4);
        System.out.println(Arrays.toString(strings));



    }
}

输出结果：[宫本4, 宫本1, 宫本3, 宫本2]；