- 动态链表
临时分配链表节点，使用完毕后释放链表节点。
优点：能及时释放空间，不使用多余内存
缺点：需要管理空间，容易出错。
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define fep(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>
using namespace std;
struct node{
int data;
node *next;
};
void solve() {
int n,m; scanf("%d %d", &n, &m);
node *head, *p, *now, *prev;
head = new node; head->data = 1; head->next = NULL;
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; //从第一个开始数
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 ;
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// freopen("C:\\Users\\24283\\CLionProjects\\untitled2\\1.in", "r", stdin);
// int _;
// cin >> _;
// while (_--)
solve();
return 0;
}
- 静态链表
预先分配一段连续空间存储链表。
有两种实现方法： - 定义结构体数组和动态链表的结构差不多
- 使用一维数组，直接在数组上进行链表操作
#include <bits/stdc++.h>
using namespace std;
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; //从第一个节点开始
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>
using namespace std;
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;
while((n--)>1){
for(int i = 1;i<m;i++) now = nodes[now].nextid;
printf("%d ",nodes[now].id);
int prev = nodes[now].preid, next = nodes[now].nextid;
nodes[prev].nextid = nodes[now].nextid;
nodes[next].preid = nodes[now].preid;
now = next;
}
printf("%d", nodes[now].nextid);
return 0;
}
- STL list
算法竞赛或工程项目中常常使用C++ STL list。list是双向链表，由标准模板库（STL）管理，通过指针访问节点数据，高效率地删除和插入。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
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){
for(int i=1;i<m;++i){
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);
it = next;
}
cout<<*it;
return 0;
}