🔗 反转链表

题目来源：206. 反转链表 – 力扣（LeetCode）

---

📌 题目描述

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

• 反转：将链表从 A → B → C → D 变为 D → C → B → A。
• 若链表为空或只有一个节点，返回其本身。

---

✅ 示例解析

示例 1：

• 输入：head = [1,2,3,4,5]
• 输出：[5,4,3,2,1]
• 解释：原链表 1→2→3→4→5，反转后变为 5→4→3→2→1。

示例 2：

• 输入：head = [1,2]
• 输出：[2,1]
• 解释：1→2 变为 2→1。

示例 3：

• 输入：head = []
• 输出：[]
• 解释：空链表反转后仍为空。

---

⚠️ 提示

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

---

💡 解法：迭代法（三指针）—— O(n) 时间，O(1) 空间

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = null; // 指向已反转部分的头节点
        while (head != null) {
            ListNode next = head.next; // 保存下一个节点
            head.next = res;           // 当前节点指向前一段反转链表
            res = head;                // 更新反转链表的头
            head = next;               // 移动到原链表的下一个节点
        }
        return res;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 每个节点被访问且仅被访问一次，总共 n 个节点。
• 空间复杂度：O(1) ✅
  • 仅使用常数个额外指针：res、next、head。
  • 无递归调用栈，空间效率极高。

---

🧩 解题思路

1. 核心思想：边遍历边反转，维护“已反转”部分的头节点
   • 使用三个关键变量：
     • head：指向原链表当前待处理的节点。
     • res：指向已反转部分的头节点（初始为 null）。
     • next：临时保存 head.next，防止断链后丢失后续节点。
2. 反转步骤（每轮操作）：java深色版本ListNode next = head.next; // 1. 保存下一个节点 head.next = res; // 2. 当前节点指向前一段反转链表 res = head; // 3. 更新反转链表的头为当前节点 head = next; // 4. 移动到原链表的下一个节点这四步实现了指针的“翻转”和“推进”。
3. 举例说明：
   对 head = [1,2,3,4,5]：步骤headresnext操作初始1→2→3→4→5null–11→…null2→3→4→51.next = null, res = 1, head = 222→…1→null3→4→52.next = 1, res = 2, head = 333→…2→1→null4→53.next = 2, res = 3, head = 444→…3→2→1→null54.next = 3, res = 4, head = 555→…4→3→2→1→nullnull5.next = 4, res = 5, head = null结束null5→4→3→2→1→null-返回 res ✅
4. 边界处理：
   • 空链表：head == null，直接返回 null。
   • 单节点：head.next == null，直接返回 head。
   • 多节点：循环处理直到 head == null。
5. 为什么 res 最终是新头？
   • res 始终指向已反转链表的头节点。
   • 每次将 head 插入到 res 前面，res 就更新为新的头。
   • 最终 res 指向原链表的最后一个节点，即新链表的头。