list是一个双向链表，可以在常数时间内插入和删除，不支持数组表示法和随机访问。使用list时，需要引入头文件#include<list>。

list的专用成员函数如下。

● merge( b )：将链表 b 与调用链表合并，在合并之前，两个链表必须已经排序，合并后经过排序的链表被保存在调用链表中， b 为空。

● remove(val)：从链表中删除val的所有节点。

● splice(pos, b )：将链表 b 的内容插入pos的前面， b 为空。

● reverse()：将链表翻转。

● sort()：将链表排序。

● unique()：将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩，因此一般先排序后去重。

其他成员函数如下。

● push_front( x )/push_back( x )： x 从链表头或尾入。

● pop_front()/pop_back()：从链表头或尾出。

● front()/back()：返回链表头或尾元素。

● insert( p , t )：在 p 之前插入 t 。

● erase( p )：删除 p 。

● clear()：清空链表。

训练　士兵队列训练

题目描述（HDU1276）： 某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队。训练的规则为从头开始进行1至2报数，凡报2的出列，剩下的向小序号方向靠拢，再从头开始进行1至3报数，凡报到3的出列，剩下的向小序号方向靠拢，继续从头开始进行1至2报数……以后从头开始轮流进行1至2报数、1至3报数，直到剩下的人数不超过3人时为止。

输入： 包含多个测试用例，第1行为测试用例数 N ，接着为 N 行新兵人数（不超过5 000）。

输出： 单行输出剩下的新兵的最初编号，编号之间有一个空格。

1. 算法设计

本题为报数问题，可以使用list解决。

（1）定义一个list，将1～ n 依次放入链表尾部。

（2）如果链表中元素大于3，则计数器cnt=1；遍历链表，如果cnt++% k ==0，则删除当前元素，否则指向下一个继续计数；首先 k =2报数，报数结束后，再 k =3报数，交替进行。

（3）按顺序输出链表中的元素，以空格隔开，最后换行。

注意 ：慎用STL的list，空间复杂度和时间复杂度都容易超出限制。 4MeZh1x/XetSeUp/9ofCtbfD/fts4jd8LJu5VDjGS21/j530xUS8Fm/uJ+rBH9s+

2. 算法实现