UVa 11988

Broken Keyboard (a.k.a. Beiju Text)

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Beginner

Problem

你的键盘出了点问题，有时候Home键或End键会自动按下，你不知道键盘出了问题，非常专心地打字，甚至连显示器都没有开。当你打开显示器之后，在你面前的是一堆混乱的文本。输入打字的序列，分别用‘[’、‘]’表示Home键和End键的输入，请输出显示器上所显示的混乱文本。（Home键会把输入光标移动到文本开头、End键会把输入光标移动到文本末尾。）

（1 ≤ 序列长度 ≤ 100,000）

Solution

链表题，利用链表插入元素的优势，记录一下插入光标的位置，把字符一个个插入就可以了。碰到Home或者End只要把插入的位置改成表头或表尾即可，如果是自己写的链表，应当记录一下表尾的位置；如果用STL，list把一且都已经帮你准备好了，代码也非常的简洁，不过在运行的时间上会慢上许多。

时间复杂度 O(N) 。