一、循环链表的原理

其实循环链表相对于单链表来讲只需要做一些小改动就好了，只需要将单链表尾结点的引用由null改为头结点就好了，这样子就形成了一个循环链表。循环链表相对于单链表来讲，可以从任意结点开始就可以遍历整个链表的所有结点，这是单链表无法做到的。

循环链表.png

二、循环链表的实现-java

public class MyCircularLinkedList {
    /**
     * 循环链表：相对普通的单链表来讲，只是修改一下末尾的结点引用，单链表末尾结点的引用为null，
     * 将其修改为头结点的位置，这样就形成了一个环，叫作循环链表。
     */
    /**
     * 循环一般具有以下功能：
     * 1.InitCircularLinkedList() 初始化操作，建立一个空的循环链表
     * 2.CircularLinkedListEmpty() 判断循环链表是否为空，为空则返回true，非空返回false
     * 3.ClearCircularLinkedList() 将循环链表清空
     * 4.CircularLinkedListInsert(T elem) 在循环链表末尾插入数据，不需要手动指定位置
     * 5.CircularLinkedListInsertWithIndex(int index,T elem) 在循环链表脚标为index处插入新元素
     * 6.CircularLinkedListDelete(int index) 删除循环链表脚标为index的元素，并返回其值
     * 7.CircularLinkedListLenth() 返回当前线性表的长度
     * 8.toString() 打印当前线性表的所有元素值，用逗号分隔
     */
    /**
     * 使用链式存储的方式来实现一个循环链表
     */
    private int CurrLenth = 0; //线性表的大小
    circularLinkedNode headNode = null; // 头结点
    private circularLinkedNode rear = null; //尾指针，方便线性表尾部的操作

    class circularLinkedNode{
        String nodeData; //存储节点数据
        circularLinkedNode next; //存储指向下一个节点的位置
    }

    public MyCircularLinkedList(){
        /**
         * 初始化一个链式存储的循环链表，生成头结点，尾指针
         */
        this.headNode = new circularLinkedNode();
        headNode.nodeData = null; //头结点的数据域不需要存储数据
        headNode.next = null; //初始化一个链式存储的线性表，由于没有第一个结点，所以头结点的next为空
        this.rear = headNode; //将尾部指针指向头结点
    }

    //实现CircularLinkedListEmpty功能
    public Boolean CircularLinkedListEmpty(){
        return CurrLenth == 0?true:false;
    }

    //实现ClearCircularLinkedList的功能
    public Boolean ClearCircularLinkedList(){
        /**
         * 由于java不能手动释放内存占用，只能依靠GC机制，所以这边需要循环
         * 将每个指向结点的引用置为空，这样当一块内存没有引用指向时，JVM
         * 会自动回收。
         */
        if (CurrLenth == 0){return true;} //空链表，直接返回true
        circularLinkedNode index = headNode.next; //该游标作用是保存释放结点前,存放该结点的指针域数据
        circularLinkedNode currIndex = headNode.next; //该游标作用是指向待释放结点对象
        if (CurrLenth == 1){
            //表示只有一个结点时
            index = null;
            currIndex = null;
            headNode.next = null;
            // 释放完以后的初始化操作
            CurrLenth = 0;
            rear = headNode;
            return true;
        }
        for (;index.next != null;){
            index = currIndex.next;
            currIndex.next = null;
            currIndex = index;
        }
        // 释放临时游标指针
        index = null;
        currIndex = null;
        // 释放头结点链接
        headNode.next = null;
        // 释放完以后的初始化操作
        CurrLenth = 0;
        rear = headNode;
        return true;
    }


    //实现CircularLinkedListInsert功能
    public Boolean CircularLinkedListInsert(String elem){
        try{
            circularLinkedNode linkedNode = new circularLinkedNode();
            linkedNode.nodeData = elem;
            linkedNode.next = headNode; //尾结点的引用指向头结点
            if (headNode.next == null){
                // 头结点为空，表示插入的是第一个结点
                headNode.next = linkedNode;
                rear = linkedNode;
                CurrLenth++;
                return true;
            }else{
                rear.next = linkedNode; //让尾指针指向下一个结点，即将该结点放于线性表最后的位置
                rear = linkedNode;
                CurrLenth++;
                return true;
            }
        }catch(Exception e){
            System.out.println("Add LinkedNode Find unknow Error!"+e);
            return false;
        }
    }



    //实现CircularLinkedListInsertWithIndex的功能
    public Boolean CircularLinkedListInsertWithIndex(int index,String elem){
        if (index <= 0 || index > CurrLenth+1){
            // 当index = CurrLenth+1时，表示需要插入到链表尾部
            return false;
        }
        int currIndex = 1; //当前脚标
        circularLinkedNode currNode = headNode.next;
        circularLinkedNode insertNode = null; //待插入的结点
        if (index == 1){
            // 表示要插入到头结点后面的第一个结点，需要修改头结点，同时也需要修改尾指针
            if (CurrLenth == 0){
                // 表示是空的循环链表
                insertNode = new circularLinkedNode();
                insertNode.nodeData = elem;
                insertNode.next = headNode;
                headNode.next = insertNode;
                rear = insertNode;
                CurrLenth++;
                return true;
            }else{
                insertNode = new circularLinkedNode();
                insertNode.nodeData = elem;
                insertNode.next = currNode;
                headNode.next = insertNode;
                CurrLenth++;
                return true;
            }
        }
        if (index == CurrLenth+1){
            //表示是插入最后结点后面的位置，这种情况需要修改尾指针
            insertNode = new circularLinkedNode();
            rear.next = insertNode;
            insertNode.nodeData = elem;
            insertNode.next = headNode;
            rear = insertNode;
            CurrLenth++;
            return true;
        }
        while (currIndex != index-1){
            // 主要是遍历出要插入的前一个结点所处的位置
            currIndex++;
            currNode = currNode.next;
        }
        circularLinkedNode nextNode = currNode.next;
        insertNode = new circularLinkedNode();
        insertNode.nodeData = elem;
        currNode.next = insertNode;
        insertNode.next = nextNode;
        CurrLenth++;
        return true;
    }

    //实现CircularLinkedListDelete的功能
    public String CircularLinkedListDelete(int index){
        if (index <=0 || index > CurrLenth){return "error";}
        int currIndex = 1;
        circularLinkedNode currNode = headNode.next;
        circularLinkedNode realseNode = null; //待释放的结点
        String returnString = null; //待返回的字符串
        if (index == 1){
            // 表示要删除头结点后面的位置，操作特殊，需要修改头结点指针域
            if (headNode.next.next != null){
                // 说明链表不止一个结点，删除第一个结点，不需要修改尾指针
                returnString = currNode.nodeData;
                realseNode = currNode;
                headNode.next = currNode.next;
                realseNode.next = null;
                CurrLenth--;
                return returnString;
            }else {
                returnString = currNode.nodeData;
                currNode.next = null;
                headNode.next = null;
                rear = headNode;
                CurrLenth--;
                return returnString;
            }
        }
        while (currIndex != index-1){
            currIndex++;
            currNode = currNode.next;
        }
        if (currIndex+1 == CurrLenth){
            // 表示删除的是最后一个结点，所以需要修改尾指针
            rear = currNode; // 首先将尾指针指向即将删除的尾结点的前一个结点
            realseNode = currNode.next;
            returnString = realseNode.nodeData;
            currNode.next = headNode; // 循环链表需要将最后一个结点的引用指向头结点
            realseNode.next = null;
            CurrLenth--;
            return returnString;
        }else{
            realseNode = currNode.next;
            returnString = realseNode.nodeData;
            currNode.next = realseNode.next;
            realseNode.next = null;
            CurrLenth--;
            return returnString;
        }
    }

    //实现CircularLinkedListLenth的功能
    public int CircularLinkedListLenth(){
        return CurrLenth;
    }

    //实现toString的功能
    public String toString(){
        StringBuffer stringBuffer = new StringBuffer();
        if (headNode.next == null){return "";} //表示是空链表
        if (headNode.next != null && headNode.next.next == headNode){
            // 表示该线性表只存在一个结点
            return headNode.next.nodeData;
        }
        for (circularLinkedNode start = headNode.next; start != headNode; start = start.next){
            if (start.next == headNode){
                //表示是最后一个结点
                stringBuffer.append(start.nodeData);
            }else{
                stringBuffer.append(start.nodeData+",");
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
    }
}

三、循环链表的应用-约瑟夫环问题

关于约瑟夫环问题
，大家可以参考一下百度百科，实现的方法也有很多种，但是都逃不开用循环链表。

笔者用java来实现，感兴趣的也可以根据自己喜好的语言来进行实现。

public class circularLinkedListTest {
    /**
     * 约瑟夫环问题，是一个经典的循环链表应用场景
     * 假设现在存在30个人，围成一个圈，给每个人编号，从1到30，现在玩一个游戏
     * 从1开始数，每数到9就将该人杀死，然后继续往后数，以此类推，求最后活下来
     * 的15个人，编号分别是多少？
     */
    public static void main(String[] args) {
        MyCircularLinkedList myCircularLinkedList = new MyCircularLinkedList();
        /**
         * 循环给循环链表插入30个值，1,2,3 - 30，并且我们还需要一个标识位，标识该人
         * 是否已经被杀死。由于自己实现的这个循环链表，每个元素值是String类型，那就
         * 采用字符串拼接的方式来存储这两个值，其实也可以用class，原理是一样的。
         */
        for (int index = 1;index <=30;index++){
            // 1：表示活着，0：表示死了，刚开始初始化30个人都活着
            myCircularLinkedList.CircularLinkedListInsert(String.valueOf(index)+":"+"1");
        }
        /**
         * 初始化完毕，开始游戏，每数到9就杀死该人
         */
        MyCircularLinkedList.circularLinkedNode headNode = myCircularLinkedList.headNode; // get循环链表头结点
        headNode.nodeData = "0:0"; //为了通用性起见，将头结点直接设置为编号0的死人。
        int survivalNumber = 30; // 存活人数
        int index = 1; // 数数游标
        String nodeData = null; //用于保存被杀死对象的编号
        MyCircularLinkedList.circularLinkedNode currNode = headNode; // 保存当前循环到的结点，初始是头结点
        while (survivalNumber != 15){
            if (index == 9){
                if (currNode.nodeData.split(":")[1].equals("0")){
                    // 表示该人早已被杀死，可以跳过
                    currNode = currNode.next;
                    continue;
                }else{
                    nodeData =  currNode.nodeData.split(":")[0];
                    currNode.nodeData = nodeData+":"+"0"; //表示该人已被杀死
                    index = 1; //复位数数游标
                    survivalNumber--; //存活人数减1
                }
            }else{
                if (currNode.nodeData.split(":")[1].equals("0")){
                    // 表示该人早已被杀死，可以跳过
                    currNode = currNode.next;
                    continue;
                }else{
                    currNode = currNode.next;
                    index++;
                }
            }
        }
        /**
         * 游戏结束，开始清理剩余活下来的人，以及对应的编号
         */
        StringBuffer survival = new StringBuffer();
        currNode = headNode.next; // 复位游标，指向第一个结点
        for (;currNode != headNode;currNode = currNode.next){
            if (currNode.nodeData.split(":")[1].equals("1")){
                if (currNode.next == headNode){
                    // 表示是最后一个结点了
                    survival.append(currNode.nodeData.split(":")[0]);
                }else{
                    survival.append(currNode.nodeData.split(":")[0]);
                    survival.append(",");
                }
            }else{continue;}
        }
        System.out.println(survival.toString().replace(","," ").trim());
    }
}