【LeetCode 热题 100】206. 反转链表——（解法一）值翻转

Problem: 206. 反转链表
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

整体思路

这段代码旨在解决一个基础且经典的链表问题：反转单链表 (Reverse Linked List)。问题要求将一个给定的单链表进行反转，并返回反转后新链表的头节点。

该算法采用了一种 “借助额外空间（数组）” 的方法来实现反转。但需要特别注意的是，它并没有真正地反转链表的指针链接，而是仅仅反转了链表节点中的值 val。这种方法在很多面试场景下可能不被接受，因为“反转链表”通常意味着改变节点的 next 指针指向。

其核心逻辑步骤如下：

1. 第一阶段：遍历并存储节点值

   • 算法首先创建了一个动态数组（ArrayList）temp，用来存储链表中所有节点的值。
   • 通过一个 while 循环，从头节点 head 开始遍历整个链表。
   • 在遍历过程中，将每个节点 p 的值 p.val 依次添加到 temp 列表中。
   • 当遍历结束后，temp 列表中就按顺序存储了原始链表的所有节点值。例如，对于链表 1 -> 2 -> 3，temp 将是 [1, 2, 3]。

2. 第二阶段：再次遍历并覆盖节点值

   • 算法将指针 p 重新置于链表的头节点 head。
   • 接着，通过一个 for 循环，从后向前地遍历 temp 列表。
   • 在循环的每一步，将 temp 列表中的值 temp.get(i) 赋给当前链表节点 p 的 val 属性 (p.val = ...)。
   • 然后，将指针 p 移动到下一个节点 (p = p.next)。
   • 这个过程实际上是用反转后的值序列，覆盖了原始链表节点的值。对于 1 -> 2 -> 3，temp 列表反向遍历是 3, 2, 1。第一次循环，head.val 被改为 3；第二次，head.next.val 被改为 2；第三次，head.next.next.val 被改为 1。
   • 最终，链表的结构（指针指向）没有变，但节点的值序列变成了 3 -> 2 -> 1。

3. 返回结果：

   • 由于链表的头节点引用 head 从未改变，直接返回 head 即可。

完整代码

/**
 * 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 {
    /**
     * 反转一个单链表。
     * 注意：此方法仅反转节点的值，而不改变节点的指针结构。
     * @param head 原始链表的头节点
     * @return 节点值反转后的链表的头节点（与原头节点是同一个对象）
     */
    public ListNode reverseList(ListNode head) {
        // temp: 使用一个列表来存储链表中所有节点的值
        List<Integer> temp = new ArrayList<>();
        // p: 用于遍历链表的指针
        ListNode p = head;
        
        // 步骤 1: 第一次遍历，将所有节点值按顺序存入列表
        while (p != null) {
            temp.add(p.val);
            p = p.next;
        }
        
        // 将指针 p 重置回头节点，准备进行第二次遍历
        p = head;
        
        // 步骤 2: 第二次遍历，将列表中的值反向写回链表节点
        // i 从列表的最后一个索引开始，向前遍历
        for(int i = temp.size() - 1; i >= 0; i--) {
            // 将反向顺序的值赋给当前节点
            p.val = temp.get(i);
            // 移动到下一个节点
            p = p.next;
        }
        
        // 返回原始的头节点，其内部的值已经被修改
        return head;
    }
}

时空复杂度

时间复杂度：O(N)

1. 第一次遍历：while (p != null) 循环遍历整个链表一次，以填充 ArrayList。如果链表有 N 个节点，这部分的时间复杂度是 O(N)。
2. 第二次遍历：for 循环也需要遍历 N 次，以将列表中的值写回链表。这部分的时间复杂度也是 O(N)。

综合分析：
算法的总时间复杂度是 O(N) + O(N) = O(N)。

空间复杂度：O(N)

1. 主要存储开销：算法创建了一个 ArrayList temp 来存储链表中所有节点的值。
2. 空间大小：如果链表有 N 个节点，temp 列表的大小也会是 N。
3. 其他变量：p, i 等变量只占用常数级别的空间，即 O(1)。

综合分析：
算法所需的额外空间主要由 temp 列表决定。因此，其空间复杂度为 O(N)。这不是一个空间最优的解法。

【LeetCode 热题 100】206. 反转链表——（解法二）指针翻转