206.反转链表

难度：简单

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路

数组支持 随机访问（Random Access），随机访问这个概念在计算机科学中被定义为：可以用同等的时间访问到一组数据中的任意一个元素。

而链表显然是不满足这个特性的。

数组反转的常见方法是：第一个元素与最后一个元素互换位置，索引持续往中间逼近，重复这个操作即可。

那么针对链表的反转操作，关键点在于让每个节点的 next 指向自己的 pre 节点。

如果再定义一个新的链表，来实现对链表元素的反转，则是对内存空间的浪费。

我的思路：

1. 从头节点开始遍历，获取当前节点、pre 节点、next 节点
   1. 让当前节点的 next 指向 pre
   2. 当前节点 = next 节点
2. 到达链表尾的时候，退出循环

我的代码（迭代法）

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;  // 前一个节点
        ListNode cur = head;  // 当前处理的节点
        ListNode next = null; // 保存cur的下一个节点
        while (cur != null) {
            next = cur.next; // 保存下一个节点
            cur.next = pre;  // 将当前节点的next指向前一个节点，实现反转
            pre = cur;       // 更新前一个节点为当前节点
            cur = next;      // 移动到下一个节点
        }
        // 当循环结束时，pre 将指向新的头节点
        return pre;
    }
}

时间复杂度：O(n)

空间复杂度：O(1)

递归法

递归法相对抽象一些，但是其实和迭代法是一样的逻辑，同样是当 cur 为空的时候递归结束，不断将 cur.next 指向 pre 的过程。

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    public ListNode reverse(ListNode pre, ListNode cur) {
        // 递归出口
        if (cur == null) return pre;
        // 递归部分
        ListNode next = null; // 保存cur的下一个节点
        while (cur != null) {
            next = cur.next;
            cur.next = pre;// 反转操作
            pre = cur;
            cur = next;
        }
        return reverse(pre, cur);
    }
}

时间复杂度: O(n)，要递归处理链表的每个节点

空间复杂度: O(n)，递归调用了 n 层栈空间

总结

如果使用 C，C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点。

当然如果使用 Java ，Python 的话就不用手动管理内存了。

注意虚拟头节点的引入，可以使代码逻辑更统一。