链表

链表的特点是用一组位于任意位置的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不连续。链表是容易理解和操作的基本数据结构，它的操作有初始化、添加、遍历、插入、删除、查找、释放等。

P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：$ n $ 个人围成一圈，从第一个人开始报数，数到 $ m $ 的人出列，再由下一个人重新从 $ 1 $ 开始报数，数到 $ m $ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈的人的编号。

思路：考虑开两个数组构建双向链表，第一个数组记录每一个人前面的那一个人的编号，记作 $ pre[i] = i - 1 $，另一个数组记录每个人后面的那一个人的编号，记作 $ nxt[i] = i + 1$，因为 $ n $个人围成一圈，所以，第 $ n $ 个人的后继为 $ 1 $，第 $ 1 $ 个人的前驱为 $ n $，即 $ pre[1] = n, nxt[n] = 1$。