循环链表及其应用_循环链表的应用

目录

1.什么是循环链表？循环链表与单链表的区别?

2.循环链表的应用有哪些？        

3.总结 

4.参考

---

1.什么是循环链表？循环链表与单链表的区别?

        循环链表是首尾相接的链表，普通链表是尾指针为空。

循环链表结构 一图胜千文

2.循环链表的应用有哪些？        

        约瑟夫环，报数游戏，现在k个人，1,2,3...n报数  比如每次报2的出圈，然后重新报数。

        解决方案:

        方案1 标记+报数  数组模拟

        方案2 使用循环链表模拟报数

 第一次出局  2  4

 第二次出局  1  5

第三次只有一个元素3  循环退出

代码如下

public static void main(String[] args) {
        //方法1:使用标记+报数器
//        int num = GetLastIndex(5,2);
        //方法2:使用循环链表  正确的返回结果是2
        int num = GetLastIndex2(5, 2);
        System.out.println(num);
    }
 
    //标记+报数器
    //初始化数组 每个元素都是1
 
    /**
     * @Description:
     * @Date: 2021/8/9 18:54
     * @Author: fuguowen
     * @Return k个人的索引的下标  比如2代表第三个人
     * @Throws
     */
    public static int GetLastIndex(int k, int p) {
        //k个人
        //p报2
        int[] arr = new int[k];
        //初始化数组都为1
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 1;
        }
        int num = arr.length;
        //报数器
        int flag = 0;
        while (num > 1) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 1) {
                    flag++;
                    if (flag == p) {
                        //数组清空
                        arr[i] = 0;
                        //报数器清空
                        flag = 0;
                        //数量减一
                        num--;
                    }
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                return i;
            }
        }
        return 0;
    }
 
    //使用循环链表模拟，报数的人删除对应的节点
    public static int GetLastIndex2(int k, int reportNum) {
        //k个人
        //构建循环链表
        Node head = CreatCycLinkedList(k);
 
        Node p = head.next;
        //队列中元素只有一个的情况是p.next=p  ☆☆☆☆☆
        while (p.next != p) {
            //p.next指向当前要删除的元素
            for (int i = 0; i < reportNum; i++) {
                p = p.next;
            }
            //删除元素
            p.next = p.next.next;
            //指针下移
            p.next = p;
        }
        return p.next.index;
    }
 
    public static Node CreatCycLinkedList(int k) {
        //构建循环链表
        Node head = new Node(-1);
        Node cur = head;
        for (int i = 0; i < k; i++) {
            cur.next = new Node(i);
            cur = cur.next;
        }
        cur.next = head.next;
        return head;
    }
 
//    参考:
//    1.https://www.cxyxiaowu.com/1159.html
 
public class Node {
    int index;
    Node next;
 
    public Node( int index) {
        this.index = index;
    }
}

3.总结 

      循环链表的主要应用在约瑟夫环，报数游戏，golang chan底层的数据节后也是循环链表等。它与单链表的区别是循环链表是尾指针指向头指针。普通单链表是尾指针指向null.

4.参考

1.https://www.cxyxiaowu.com/1159.html

     我是厚积薄发， 您的一键三连是我最大的创作动力，请一键三连，如有问题，请留言。