动态链表
#include <bits/stdc++.h>
struct node{ //定义链表结点
int data; //结点的值
node *next; //单向链表，只有一个next指针
};
int main(){
int n,m; scanf("%d %d",&n,&m);
node *head,*p,*now,*prev; //定义变量
head = new node; head->data = 1; head->next=NULL; //分配第一个结点，数据置为1
now = head; //当前指针是头
for(int i=2;i<=n;i++){
p = new node; p->data = i; p->next = NULL; //p是新结点
now->next = p; //把申请的新结点连到前面的链表上
now = p; //尾指针后移一个
}
now->next = head; //尾指针指向头：循环链表建立完成
//以上是建立链表，下面是本题的逻辑和流程。
now = head, prev = head; //从第1个开始数
while((n--) >1 ){
for(int i=1;i<m;i++){ //数到m，停下
prev = now; //记录上一个位置，用于下面跳过第m个结点
now = now->next; // ↵
}
printf("%d ", now->data); //输出第m结点，带空格
prev->next = now->next; //跳过这个结点
delete now; //释放结点
now = prev->next; //新的一轮
}
printf("%d", now->data); //打印最后一个，后面不带空格
delete now; //释放最后一个结点
return 0;
}
笔记：动态链表的链表节点可以现取现用，不会有多余的内存浪费，但是存储空间不一定连续，而且不用的节点空间要及时释放掉。
单向静态链表
#include <bits/stdc++.h>
const int N = 105; //定义静态链表的空间大小
struct node{ //单向链表
int id, nextid; //单向指针
//int data; //如有必要，定义一个有意义的数据
}nodes[N]; //定义在全局的静态分配
int main(){
int n, m; scanf("%d%d", &n, &m);
nodes[0].nextid = 1;
for(int i=1;i<=n;i++){ nodes[i].id = i; nodes[i].nextid = i + 1;}
nodes[n].nextid = 1; //循环链表：尾指向头
int now = 1, prev = 1; //从第1个开始
while((n--) >1){
for(int i=1;i<m;i++){ prev = now; now = nodes[now].nextid;} //数到m停下
printf("%d ", nodes[now].id); //带空格打印
nodes[prev].nextid = nodes[now].nextid; //跳过结点now，即删除now
now = nodes[prev].nextid; //新的now
}
printf("%d", nodes[now].nextid); //打印最后一个，后面不带空格
return 0;
}
笔记：静态列表的“连续空间”对链表来说无意义，链表的指针可以直接指向下一个节点的地址，链表节点不要超出链表的空间范围
双向静态链表
#include <bits/stdc++.h>
const int N = 105;
struct node{ //双向链表
int id; //结点编号
//int data; //如有必要，定义一个有意义的数据
int preid, nextid; //前一个结点，后一个结点
}nodes[N];
int main(){
int n, m; scanf("%d%d", &n, &m);
nodes[0].nextid = 1;
for(int i = 1; i <= n; i++){ //建立链表
nodes[i].id = i;
nodes[i].preid = i-1; //前结点
nodes[i].nextid = i+1; //后结点
}
nodes[n].nextid = 1; //循环链表：尾指向头
nodes[1].preid = n; //循环链表：头指向尾
int now = 1; //从第1个开始
while((n--) >1){
for(int i=1;i<m;i++) now = nodes[now].nextid; //数到m，停下
printf("%d ", nodes[now].id); //打印，后面带空格
int prev = nodes[now].preid, next = nodes[now].nextid;
nodes[prev].nextid = nodes[now].nextid; //删除now
nodes[next].preid = nodes[now].preid;
now = next; //新的开始
}
printf("%d", nodes[now].nextid); //打印最后一个，后面不带空格
return 0;
}
笔记：双向链表有两个指针，一个指向下一个节点，一个指向上一个节点，不仅可以查到下一个节点，还可以“溯源”找到上一个节点，有这两个节点就可以实现“自我删除”
一维数组（单向静态链表）
#include<bits/stdc++.h>
int nodes[150];
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i=1;i<=n-1;i++) nodes[i]=i+1; //nodes[i]的值就是下一个结点
nodes[n] = 1; //循环链表：尾指向头
int now = 1, prev = 1; //从第1个开始
while((n--) >1){
for(int i = 1; i < m; i++){ //数到m，停下
prev = now; now = nodes[now]; //下一个
}
printf("%d ", now); //带空格
nodes[prev] = nodes[now]; //跳过结点now，即删除now
now = nodes[prev]; //新的now
}
printf("%d", now); //打印最后一个，不带空格
return 0;
}
笔记：数组的每个元素地址是连续的，类似于静态链表，下一个节点的位置也是通过数组的下标就能获得
STL list
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m; cin>>n>>m;
list<int>node;
for(int i=1;i<=n;i++) node.push_back(i); //建立链表
list<int>::iterator it = node.begin(); //迭代器
while(node.size()>1){ //list的大小由STL自己管理
for(int i=1;i<m;i++){ //数到m
it++;
if(it == node.end()) it = node.begin(); //循环：到末尾了再回头
}
cout << *it <<" ";
list<int>::iterator next = ++it;
if(next==node.end()) next = node.begin(); //循环链表
node.erase(--it); //删除这个结点，node.size()自动减1
it = next;
}
cout << *it;
return 0;
}
笔记：c++里的STL list 是双向的循环链表，使用起来很方便，不需要再自己建立结构体数组写链表，直接放进去数据就能使用，遍历list要记得用迭代器遍历