题解 | #孩子们的游戏(圆圈中最后剩下的数)#

public class Solution {

    public class ListNode {
        public int val;
        public ListNode next;
        public ListNode pre;
        public ListNode(int val) {
            this.val = val;
        }
    }

    public int LastRemaining_Solution(int n, int m) {

        // 一些特殊情况的处理
        if (1 == n) {
            return 0;
        }

        // 小朋友们围成一圈
        // 初始化
        ListNode head = new ListNode(0);
        ListNode node = head;
        // 围成一圈
        for (int i = 1; i < n; i++) {
            ListNode tmp = new ListNode(i);
            tmp.pre = node;
            node.next = tmp;
            node = tmp;
        }
        head.pre = node;
        node.next = head;

        node = head;

        int account = 0;
        while (node.next != node) {
            account++;
            if (account ==
                    m) { // 当某名小朋友喊到 m 时，这名小朋友就要出队唱歌，同时可以拿礼物，并且不再回到圈中
                ListNode preNode = node.pre;
                ListNode nextNode = node.next;
                preNode.next = nextNode;
                nextNode.pre = preNode;
                account = 0; // 别忘了，计数器要重新归为 0
                node = nextNode;
            } else {
                node = node.next;
            }
        }
        return node.val;
    }
}