算法题..链表

Question

场景如下:-

我想反转单链表的方向，换句话说，反转后所有指针现在应该指向后..

这个算法应该需要线性时间。

我想到的解决方案是使用另一个数据结构 A Stack.. 借助它可以轻松反转单向链表，所有指针都指向后方.. 但我怀疑以下实现是否成功线性时间复杂度。请对此发表评论。如果有其他有效的算法，请讨论。

谢谢。

Answer 1

你可以这样做:只要输入列表中有节点，就移除它的第一个节点并将其插入到输出列表的开头:

node* reverse(node *in) {
   out = NULL;
   while (in) {
      node = in;
      in = in->next;
      node->next = out;
      out = node;
   }
   return out;
}