反转链表考察你对指针操作、数据结构基础以及逐步推理状态变化的能力。它是各级编程面试中最常被问到的问题之一。
先和面试官确认是要迭代解法、递归解法还是两种都要。
迭代法：使用三个指针（prev、current、next），遍历链表逐个反转指向。
递归法：先递归反转剩余链表，再修复头节点指针。
分析时间复杂度 O(n)，迭代空间 O(1)，递归空间 O(n)（调用栈）。
迭代反转单链表时，我初始化三个指针：prev 为 null，current 为 head，next 为 null。遍历链表时，每一步先保存 current.next 到 next，再将 current.next 指向 prev，然后 prev 前进到 current，current 前进到 next。当 current 为 null 时，prev 就是新的头节点。时间复杂度 O(n)，空间 O(1)。递归方法则是递归到链表末尾，在回溯过程中将每个节点的 next 指向前一个节点，基准情况是节点为 null 或没有 next。递归版本时间也是 O(n)，但由于调用栈占用 O(n) 空间。生产环境中我更倾向迭代法，避免链表过长时栈溢出。
在白板上画出指针变化过程，可视化思考可以防止越界错误。
始终处理边界情况：空链表、只有一个节点的链表。
说明原地反转优于新建链表，节省内存。
可以。迭代三指针法只需 O(1) 额外空间即可原地反转。
通常迭代更优，因为它只用 O(1) 空间，且不会在长链表上导致栈溢出。
对每个节点交换 prev 和 next 指针，最后将 head 指向原来的尾节点即可。