蒟蒻盲猜$O$($n$)（大雾弥漫
by 豌豆射手皮0608 @ 2019-05-19 21:14:30
O(n)。。。
by Ameiyo @ 2019-05-19 21:17:01
线性，他不会打翻转标记
by cosmicAC @ 2019-05-19 21:17:17
[看下这道题](https://cn.vjudge.net/problem/HDU-6375)
以及 leaderboard 的第一份代码。。。
如果是数据水的话我就不说话了，因为似乎考试的时候也有人暴力卡过去。。。
by Ameiyo @ 2019-05-19 21:18:20
@[SarvaTathagata](/space/show?uid=30093) 所以目测是数据水了嘛。。。
by Ameiyo @ 2019-05-19 21:18:47
forward_list 一定是O(n)
list 理论上可以O(1)，实际看编译器实现吧
by saipubw @ 2019-05-19 21:58:07
在网上找了下源码，翻了好久，发现 reverse 似乎是线性的（do {} while（）） 。
[C++ STL源码学习(list篇）](https://blog.csdn.net/yuanliang01xiaolang/article/details/39644957)
@[saipubw](/space/show?uid=128307) 理论上可以 O(1) 是怎么做到的？求教。
只打反转标记的话，在 splice 函数中不是要整个遍历一遍吗，应该等同于线性吧嘤嘤嘤。
by Ameiyo @ 2019-05-19 22:11:46
问了下我们老师，老师看了源码也说是 O(n) 的
估计应该就是线性的
但是心里没底不敢结贴嘤嘤嘤
by Ameiyo @ 2019-05-19 22:17:29
@[Ameiyo](/space/show?uid=39947) 存一个flag，反转之后改掉flag和头节点即可（预先存下头尾节点）
by saipubw @ 2019-05-19 22:17:57
@[Ameiyo](/space/show?uid=39947) 接下来根据flag判断两个指针那个是left那个是right，不过说实话这个做法实用度不高，增加了其他操作的常数。所以编译器应该不会这么写
by saipubw @ 2019-05-19 22:18:54