剑指offer - 孩子们的游戏(圆圈中最后剩下的数)

题目描述：https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&&tqId=11199&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

• 思路分析：使用单向环形链表解决问题。
  • 创建环形链表
    • 首先创建一个指针 first 用来标记第一个结点，然后创建一个辅助结点 curNode 指向当前环形链表的最后一个结点。
    • 当添加第一个结点的时候，让 frist 指针和 curNode 指针都指向新创建的节点。
    • 接下来进行插入新结点 newNode 操作：
      • curNooe.next = newNode;
      • newNode.next = first;
      • curNode = newNode;
  • 根据用户输入让一次删除其中的数字，直到环形链表中只剩下一个结点。
    • 创建辅助指针 preFirst 指向 first 的前面一个结点。
    • 当 preFirst != first 的时候说明圈中至少有两个结点，那么就可以进行移动，两个指针同时移动。
    • 当找到要删除的结点的时候
      • 如果需要记录当前结点，首先记录下来，然后进行删除操作
      • first = first.next
      • preFirst.next = first

★ 图解
  ★ 创建环形链表

  ★ 删除结点

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) return -1;
        List list = new List();
        list.add(n); // 创建链表
        // list.list();
        return list.solution(n, m); // 出圈
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        System.out.println(new Solution().LastRemaining_Solution(n, m));
    }
}
class List {
    Node first = null, curNode = null;
    public void add(int n) { // 创建环形链表
        for (int i = 0; i < n; ++ i) {
            Node node = new Node(i);
            if (i == 0) {
                first = node;
                curNode = first;
            }
            curNode.next = node;
            node.next = first;
            curNode = node;
        }
    }
    public void list () {
        Node cur = first;
        while (cur.next != first) {
            System.out.println(cur);
            cur = cur.next;
        }
        System.out.println(cur);
    }
    public int solution(int n, int m) {
        Node preFirst = first;
        while (preFirst.next != first) {
            preFirst = preFirst.next;
        }
        while (preFirst != first) {
            for(int i = 0; i < m - 1; ++ i) {
                first = first.next;
                preFirst = preFirst.next;
            }
            first = first.next;
            preFirst.next = first;
        }
        return first.no;
    }
}
class Node {
    public int no;
    public Node next;
    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" + "no=" + no + '}';
    }
}