algorithm - 在常量空间和线性时间中向后打印单链表

Question

听到一道面试题:

"Print a singly-linked list backwards, in constant space and linear time."

我的解决方案是原地反转链表，然后像这样打印它。是否有另一种非破坏性的解决方案？

Answer 1

你已经想出了大部分答案:原地反转链表，遍历链表回到开头打印它。为防止它(永久)破坏性，在将链表遍历到开头并打印时，再次反转链表。

但是请注意，这仅在您只有一个执行线程或将整个遍历设置为关键部分以便一次只有一个线程执行时才有效(即，第二个线程永远无法执行列表在遍历的中间)。