# 圈圈中最后剩下的数字|博客系列

> 本文详细讲解了“圈圈中最后剩下的数字”问题的题目描述、解题思路及两种常见解法（链表法和数组模拟法），并提供了JavaScript代码实现，适合数据结构与算法学习者参考。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/27-%E5%9C%88%E5%9C%88%E4%B8%AD%E6%9C%80%E5%90%8E%E5%89%A9%E4%B8%8B%E7%9A%84%E6%95%B0%E5%AD%97
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

### 题目描述

`0,1,...,n-1`这`n`个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第`m`个数字。求出这个圆圈里剩下的最后一个数字。

### 解题思路

**解法一:链表解法**

1. 先创建一个`n`长度的环形链表;
2. 记录下节点头的前一个节点`current`,以保证我们找到需要删除的节点是`current.next`;
3. 每次循环`m`找到目标节点进行删除,终止条件为节点的`next`为它自己;
4. 时间复杂度为`O(m*n)`,空间复杂度为`O(n)`.

**解法二:用数组模拟**

每次计算下标，需要考虑末尾条件

### coding

**解法一**

```javascript
/*
* 圈圈中最后一个数字
* @params{Number} m
* @params{Numner} n
* @returns{Number}
*/
function LastRemaining_Solution(n, m) {
    if (n < 1 || m < 1) return -1

    let loop = createListNodeLoop(n)

    while (loop != loop.next) {
        for (let i = 0; i < m - 1; i++) {
            loop = loop.next
        }
        loop.next = loop.next.next
    }
    return loop.val
}

function createListNodeLoop(n) {
    let head = {
        val: 0
    }
    let current = head
    for (let i = 1; i < n; i++) {
        current.next = {
            val: i
        }
        current = current.next
    }
    current.next = head
    return current
}
```

**解法二**

```javascript
/*
* 圈圈中最后一个数字
* @params{Number} m
* @params{Numner} n
* @returns{Number}
*/
function LastRemaining_Solution(n, m) {
    if (n < 1 || m < 1) return -1

    let array = Array.from({
        length: n
    }, (item, index) => index)

    let index = 0;
    while (array.length > 1) {
        index = (index + m) % array.length - 1
        if (index >= 0) {
            array.splice(index, 1)
        } else {
            array.splice(array.length - 1, 1)
            index = 0
        }
    }
    return array[0]
}
```

**测试代码**

```javascript
LastRemaining_Solution(10, 2)
// 4
```
