@[saipubw](/space/show?uid=128307) 只改头结点可以吗，所有点的前驱与后继都不是都应该交换吗？
by Ameiyo @ 2019-05-19 22:19:24
@[Ameiyo](/space/show?uid=39947) 不需要，根据flag判断那个是left，那个是right
by saipubw @ 2019-05-19 22:21:05
@[saipubw](/space/show?uid=128307) 根据 flag 判断的话在 splice 函数中该怎么办？
每个点还是都要遍历一次。
splice 中的 transfer 是改结点的前驱后继而做到的，因此是 O(1) 。
给每个点一个 flag 改标记的时候也是线性的吧。
by Ameiyo @ 2019-05-19 22:23:23
@[saipubw](/space/show?uid=128307) 抱歉，我意识到一些问题。
我们在实现的时候是可以这么写。
但是 STL 中的 list 石锤线性。
by Ameiyo @ 2019-05-19 22:24:25
@[Ameiyo](/space/show?uid=39947) 整个链表就一个flag啊，干嘛要每个节点一个flag
前驱后继不就是left[node] right[node]就知道了
by saipubw @ 2019-05-19 22:25:33
@[Ameiyo](/space/show?uid=39947) 还想不明白建议自己手写一个
by saipubw @ 2019-05-19 22:25:47
@[Ameiyo](/space/show?uid=39947) 对啊，所以我说stl不会这么做
by saipubw @ 2019-05-19 22:26:35
所以自己写 list 的时候是可以打标记，但是合并的时候可能会麻烦。
考试的时候我的想法是，保证头尾的前后指针正确，每次找前后结点时判断一下要找的结点的数据是否正确（根据头或尾），不正确就交换。
但是我打挂了。。。
by Ameiyo @ 2019-05-20 11:51:30
所以现在差不多应该可以结贴了。。。
# STL 的 list 的 reverse 是线性的。
by Ameiyo @ 2019-05-20 11:53:54
@[saipubw](/space/show?uid=128307) 还有一个问题，如果要把一个列表接到另一个列表后面，翻转之后要怎么操作？（用 flag 或别的）
by Ameiyo @ 2019-05-20 11:56:01