O(1)时间复杂度下反转一个链表

在传统的反转链表的方法中，我们直接从头到尾扫描一次链表，然后挨个调整指针来实现反转。这种做法的时间复杂度是O(n)，其中n为链表的长度。

但可以通过最优解来实现O(1)时间复杂度下反转一个链表。具体的方法是，使用三个指针对链表进行重排。假设我们要反转一个由节点a1, a2, a3, a4组成的链表，按照顺序，每次将a2插入到a1的前面，a3插入到a2的前面，以此类推：

原来的链表：a1 -> a2 -> a3 -> a4 重排后的链表：a4 -> a3 -> a2 -> a1

下面是示例代码：

struct ListNode { int value; ListNode* next; };

ListNode* reverseList(ListNode* head) { if (head == nullptr) { return nullptr; }

ListNode* cur = head; // 当前节点
ListNode* prev = nullptr; // 上一个节点
ListNode* next = nullptr; // 下一个节点
while (cur != nullptr) {
    next = cur->next; // 保存下一个节点
    cur->next = prev; // 指针反转
    prev = cur; // 上一个节点移位
    cur = next; // 当前节点移位
}

return prev;

}