是否可在O(1)时间复杂度下实现Linked List（链表）反转？

结论是：常规链表的物理反转无法在O(1)时间复杂度下实现，具体理论依据如下：

• 时间复杂度是描述算法耗时随输入规模增长的变化趋势，链表反转的输入规模n就是链表的节点总数。
• 单链表的每个节点仅持有下一个节点的指针，没有随机访问能力。反转操作要求把每个节点的next指针指向它的前驱节点，你必须遍历到每一个节点才能完成指针修改，这一步的开销必然和节点数n成正比，时间复杂度最低就是O(n)。
• 即便是双向链表，反转时也需要遍历所有节点交换prev和next指针的指向，时间复杂度依然为O(n)。

有一个例外场景：如果你自定义了特殊的链表结构，额外维护了遍历方向标记、或者仅通过修改头尾指针的定义来实现逻辑上的反向遍历，完全不修改节点的内部指针，这种「逻辑反转」确实可以做到O(1)，但这不属于行业默认的链表反转（物理修改节点指针）的范畴。

内容的提问来源于stack exchange，提问作者user14101590