algorithm - 反转替代元素并附加到列表末尾

Question

给定一个链表 a->x->b->y->c->z ，我们需要反转备用元素并追加到列表末尾。即，将其输出为 a->b->c->z->y->x。

我有一个 O(n) 的解决方案，但它需要额外的内存，我们取 2 个列表并分别用替代元素填充它，所以这两个列表是 a b c 和 x y z 然后我们将反转第二个列表并将它附加到first 的尾部，使其变为 a b c z y x 。

我的问题是我们可以就地进行吗？或者是否有任何其他相同的算法？

Answer 1

基本思想:

存储x。
使a指向b。
使 y 指向存储的元素 (x)。
使b指向c。
等等
最后，让奇数位置的最后一个元素指向存储的元素。

伪代码:(简化的列表末尾检查可读性)

current = startOfList
stored = NULL
while !endOfList
  temp = current.next
  current.next = current.next.next
  temp.next = stored
  stored = temp
  current = current.next
current.next = stored

复杂性:

O(n) 时间，O(1) 空间。