一道面试题

quxiaoyong

今天参加某公司的网上笔试。一共有四道题目，其他三道倒还觉得不难，很快就作出来了。而有一道，开始也觉得不难，不过做着做着，却发现没自己想象那么简单。

题目大意是：
  实现一个可以增加一个节点、删除某个区间的节点、修改某个节点、undo和redo的链表。

  增加、删除和修改节点，相信学过数据结构的都觉得不难，至少可以用自己的方式哪怕是最简单的方式去实现。难就难在undo和redo上。刚看到题目，我也想到了undo是需要用栈来存储操作的，而redo貌似是用队列来存储操作。

  做了该题，发现自己诸多不足。在此发帖，诚邀各路高手参与讨论，小弟愚昧，自己的实现暂不贴出。

freearth

回复 1# quxiaoyong
我理解的，redo是指做了操作a，undo（撤销操作a），之后做redo（重做操作a）这个意思吧。

我觉得你已经回答对了，用个类似的栈结构就可以了，这个栈只保存最近的K的操作，在undo的时候，不要立刻弹栈，而是使用另一个指针从栈顶向栈底做undo，如果需要做redo，仍然使用这个指针向栈顶做redo。直到下一个“真实”操作。当下一个“真实”操作出现时，弹出从栈顶到当前指针的所有元素，再这个新操作压栈。