题目链接

三种方式

• 第一种：在堆上构造链表并模拟删除过程
  • 时间复杂度：
  • 空间复杂度：
• 第二种：基于数组构造链表并模拟删除过程
  • 时间复杂度：
  • 空间复杂度：
• 第三种：递推公式
  • 时间复杂度：
  • 空间复杂度：

第一种：在堆上构造链表并模拟删除过程

这种方法是最直观的了。首先，定义如下结构体，用于存储链表。

    struct Node {
        Node(int v = 0) : val(v), next(nullptr) {}
        int val; // 数据域
        Node *next; // 指针域
    };

接着，通过尾插法构造链表。

此时，我们构造出了具备 n 个节点的链表。然后，我们将第 n 个节点的 next 指针指向第一个节点，这样就获得了一个环形链表。接下来，开始模拟删除过程。

单链表的删除操作也很简单：设待删除节点为 cur, 其前驱节点为 pre，即 pre->next 指向 cur。在单向链表中，通过修改 pre->next = cur->next 即可删除 cur 节点。

因为需要操作待删除节点的前驱节点，初始时不妨将 pre 指向第一个节点的前驱节点。这样才经过 m-1 次 pre=pre->next 的移动操作后，pre 的后继节点即为要删除的节点，此时通过修改 pre->next = pre->next->next 即可完成一次删除。

值得注意的是，在完成一次删除后，pre 恰巧仍指向下一轮游戏的第一个节点的前驱节点，也就是说，此时的 pre 仍然满足初始时位置要求。因此我们无需做任何调整，直接进行下一轮的 m-1 次移动操作和删除操作即可。

在经过 n-1 轮上述操作后，游戏结束，此时 pre 指向的节点即为答案。

下面为完整的代码实现，耗时 290ms。

class Solution {
public:
    struct Node {
        Node(int v = 0) : val(v), next(nullptr) {}
        int val;
        Node *next;
    };
    int ysf(int n, int m) {
        Node dummy, *tail = &dummy;
        for (int i = 1; i <= n; i++) {
            tail->next = new Node(i);
            tail = tail->next;
        }
        tail->next = dummy.next;
        Node *pre = &dummy;
        while(n > 1) {
            for (int i = 1; i < m; i++, pre = pre->next) {}
            auto tmp = pre->next;
            pre->next = pre->next->next;
            delete tmp;
            n--;
        }

        return pre->val;
    }
};

第二种：基于数组构造链表并模拟删除过程

在严蔚敏，吴伟民编著的《数据结构》一书中，提到了一种基于数组实现链表的方法。这种方法的好处是可一次性分配所有节点的内存，避免了在增删过程中频繁的 new/delete，进而提高程序的效率。当然缺点也很明显，当节点数量超过数组的容量时，需重新分配更大的数组并进行大量的复制。

该题预先知道节点数量的上限为 ，因此先构造一个长度为 的数组 next 用于存储链表。

pair<int, int> node[10000];

其中，first 为值域，second 为指针域。

class Solution {
public:
    pair<int, int> node[10000];
    int ysf(int n, int m) {
        for (int i = 0; i < n; i++) {
            node[i].first = i+1;
            node[i].second = (i == n-1 ? 0 : i+1);
        }
        int pre = n-1;
        while (n > 1) {
            for (int i = 1; i < m; i++, pre = node[pre].second) {}
            node[pre].second = node[node[pre].second].second;
            n--;
        }
        return node[pre].first;
    }
};

class Solution {
public:
    int next[10000];
    int ysf(int n, int m) {
        for (int i = 0; i < n; i++) {
            next[i] = (i == n-1 ? 0 : i+1);
        }
        int pre = n-1;
        while (n > 1) {
            for (int i = 1; i < m; i++, pre = next[pre]) {}
            next[pre] = next[next[pre]];
            n--;
        }
        return pre+1;
    }
};

4ms

class Solution {
public:
    int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        return (m + f(n-1, m)) % n;
    }
    int ysf(int n, int m) {
        return f(n,m)+1;
    }
};