单向环形链表

循环链表

循环链表跟单链表的区在尾结点指针是指向链表的头结点。和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，采用循环链表实现代码会简洁很多。

Josephu问题

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数✋，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

👉思路：

用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

约瑟夫环 51Nod - 1073

例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。

Input

1	2个数N和K，表示N个人，数到K出列。(2 <= N, K <= 10^6)

Output

最后剩下的人的编号

Sample Input

3 2

Sample Output

对于这道OJ题可以通过递归的方法，找到其中的规律便可AC，代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + k) % i;
        }
        System.out.println(ans + 1);
    }
}

👉以此题为例，使用单项循环链表的方式实现，但是不能作为此题AC的代码，会超时！思路如下：

首先构建一个单向的环形链表

先创建第一个节点, 让 first 指向该节点，并形成环形⚪
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.f

然后进行报数出圈

需要创建一个辅助指针(变量) helper , 首先让其指向环形链表的最后这个节点
当开始报数时，让first 和 helper 指针同时的移动 k - 1 次 🐌🐌
这时就可以将first 指向的节点出圈
first = first .next
helper.next = first
然后直到圈内只有最后一个人，即最后一个节点的时候（first == helper）结束循环🔄
最后的first中的编号即为最后一个人的编号

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        addNode(n);
        countNode(n, k);

    }
    public static Node first = null; 
    public static void addNode(int nums) {
        Node current = null; // 辅助指针
        //创建一个循环链表
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i);
            if (i == 1) { //first指向第一个孩子
                first = node;
                first.next = first;
                current = first; //
            } else {
                current.next = node;
                node.next = first;
                current = node;
            }
        }
    }
    
    public static void countNode(int nums, int k) {
        //创建一个辅助指针helper
        Node helper = first;
        //需要创建一个辅助指针helper，事先应该指向环形链表的最后这个节点
        while (true) {
            if (helper.next == first) { //说明helper指向最后一个节点
                break;
            }
            helper = helper.next;
        }
        //当报数时，让first 和 helper指针同时移动 k- 1次，然后出圈
        //这是一个循环操作，直到圈中只有一个节点
        while (true) {
            if (first == helper) {//说明圈中只有一个节点
                break;
            }
            for (int i = 0; i < k - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            //这是first指向的节点，就是要出圈的节点
            first = first.next;
            helper.next = first;
        }
        System.out.println(first.no);
    }
}

//创建一个Node节点类
class Node {
    public int no;
    public Node next;
    public Node(int no) {
        this.no = no;
    }
}