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

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

迭代

迭代：开始循环-执行本状态的操作-进入到下个状态-执行本状态的操作-……-进入到下个状态-结束循环

用三个变量分别记录当前节点cur、当前节点的前一个节点pre和后一个节点tmp。每次操作都把cur和pre的关系反转，然后前进一位，再反转，再前进，直到cur=null为止。

之所以需要用tmp存储后一个节点是因为反转后cur需要前进一步，而前进的代码是cur=cur.next，但是此时cur.next=pre（反转所做的事），所以需要事先把cur的后一个节点存起来。

// 迭代：
class Solution {
    public ListNode reverseList(ListNode head) {
        // 申请节点 pre 和 cur，pre 指向 null
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null; // 这里把null改成head也行
        
        while (cur != null) {
            // 记录当前节点的下一个节点
            next = cur.next;
            // 然后将当前节点指向 pre
            cur.next = pre;

            // pre 和 cur 节点都前进一位
            pre = cur;
            // cur前进不能用cur=cur.next，因为刚才已经把cur指向pre了。这里就体现出tmp的意义了。
            cur = next;
        }
        // 注意结束条件是cur=null，此时pre指向末尾节点
        return pre;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
• 空间复杂度：O(1)。

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件是当前为空，或者下一个节点为空
        // head == null 不能省略，因为传的参数可能是空。
        if (head == null || head.next == null) {
            return head;
        }
        
        // 这里的cur就是最后一个节点，因为方法里没有对 cur 进行操作，所以第一个方法的返回值就是最后一个方法的返回值，即最后一个节点（根据结束条件得到）。
        ListNode cur = reverseList(head.next); 
        例如 head=1，子递归把1->2->3->4->5
        // 变成了 1->2<-3<-4<-5，返回 5，此时需要把2指向1，而不是5指向1。
        head.next.next = head;
        // 防止链表循环，需要将head.next设置为空
        // 上面只是把 2 指向了 1，实际上 1 还是指向 2 的：1-><-2<-3<-4<-5，
        // 所以出现了循环，所以需要将 1 指向 null：1<-2<-3<-4<-5
        head.next = null; 
        // 每层递归函数都返回cur，也就是最后一个节点，即最终链表的头节点。
        return cur;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。