反转链表

1. 问题描述

1.1 基本问题

给定一个单链表的头节点 head，反转链表，并返回反转后的链表。

示例：

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

1.2 链表节点定义

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; }
}

2. 解法分析

2.1 迭代法（推荐）

核心思想： 使用三个指针 prev、curr、next 来逐个反转节点的指向关系。

算法步骤：

1. 初始化 prev = null，curr = head
2. 遍历链表，对每个节点：
   • 保存下一个节点：next = curr.next
   • 反转当前节点指向：curr.next = prev
   • 移动指针：prev = curr，curr = next
3. 返回 prev（新的头节点）

代码实现：

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;  // 保存下一个节点
            curr.next = prev;           // 反转当前节点指向
            prev = curr;                // 移动prev指针
            curr = next;                // 移动curr指针
        }
        
        return prev;  // prev成为新的头节点
    }
}

图解过程：

初始状态：
null <- prev    curr -> 1 -> 2 -> 3 -> 4 -> 5 -> null

第一步：
null <- 1    prev    curr -> 2 -> 3 -> 4 -> 5 -> null

第二步：
null <- 1 <- 2    prev    curr -> 3 -> 4 -> 5 -> null

...

最终状态：
null <- 1 <- 2 <- 3 <- 4 <- 5 <- prev    curr(null)

2.2 递归法

核心思想： 递归到链表末尾，然后在回溯过程中逐层反转节点指向。

算法步骤：

1. 递归终止条件：head == null || head.next == null
2. 递归反转后续链表，获得新头节点
3. 反转当前节点与下一节点的指向关系
4. 返回新头节点

代码实现：

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转后续链表
        ListNode newHead = reverseList(head.next);
        
        // 反转当前节点指向
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
}

递归过程分析：

原链表：1 -> 2 -> 3 -> 4 -> 5

递归调用栈：
reverseList(1) {
    reverseList(2) {
        reverseList(3) {
            reverseList(4) {
                reverseList(5) -> 返回5
            }
            // 4.next.next = 4 即 5.next = 4
            // 4.next = null
            // 返回5，此时链表：5 -> 4
        }
        // 3.next.next = 3 即 4.next = 3
        // 3.next = null
        // 返回5，此时链表：5 -> 4 -> 3
    }
    // 2.next.next = 2 即 3.next = 2
    // 2.next = null
    // 返回5，此时链表：5 -> 4 -> 3 -> 2
}
// 1.next.next = 1 即 2.next = 1
// 1.next = null
// 返回5，最终链表：5 -> 4 -> 3 -> 2 -> 1

2.3 栈辅助法

核心思想： 利用栈的后进先出特性，先将所有节点入栈，再依次出栈重建链表。

代码实现：

import java.util.Stack;

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        
        Stack<ListNode> stack = new Stack<>();
        
        // 将所有节点入栈
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        
        // 重建反转后的链表
        ListNode newHead = stack.pop();
        curr = newHead;
        
        while (!stack.isEmpty()) {
            curr.next = stack.pop();
            curr = curr.next;
        }
        
        curr.next = null;  // 最后一个节点指向null
        return newHead;
    }
}

3. 复杂度分析

方法	时间复杂度	空间复杂度	优缺点
迭代法	O(n)	O(1)	最优解，空间效率高
递归法	O(n)	O(n)	代码简洁，但有递归栈开销
栈辅助法	O(n)	O(n)	思路直观，但额外空间开销大

4. 边界情况处理

4.1 测试用例

public class TestReverseList {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：空链表
        ListNode result1 = solution.reverseList(null);
        System.out.println("空链表：" + (result1 == null ? "null" : "非null"));
        
        // 测试用例2：单节点链表
        ListNode single = new ListNode(1);
        ListNode result2 = solution.reverseList(single);
        System.out.println("单节点：" + result2.val);
        
        // 测试用例3：多节点链表
        ListNode head = createList(new int[]{1, 2, 3, 4, 5});
        ListNode result3 = solution.reverseList(head);
        printList(result3);  // 输出：5 -> 4 -> 3 -> 2 -> 1
    }
    
    // 辅助方法：创建链表
    public static ListNode createList(int[] vals) {
        if (vals.length == 0) return null;
        
        ListNode head = new ListNode(vals[0]);
        ListNode curr = head;
        
        for (int i = 1; i < vals.length; i++) {
            curr.next = new ListNode(vals[i]);
            curr = curr.next;
        }
        
        return head;
    }
    
    // 辅助方法：打印链表
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

5. 变种问题

5.1 反转链表前N个节点

问题： 反转链表的前N个节点。

public class Solution {
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) return head;
        
        ListNode last = reverseN(head.next, n - 1);
        ListNode successor = head.next.next;
        
        head.next.next = head;
        head.next = successor;
        
        return last;
    }
}

5.2 反转链表指定区间

问题： 反转从位置 m 到 n 的链表。

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    
    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) return head;
        
        ListNode last = reverseN(head.next, n - 1);
        ListNode successor = head.next.next;
        
        head.next.next = head;
        head.next = successor;
        
        return last;
    }
}

5.3 K个一组反转链表

问题： 给定链表，每k个节点一组进行翻转。

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        
        ListNode a = head, b = head;
        
        // 找到第k+1个节点
        for (int i = 0; i < k; i++) {
            if (b == null) return head;  // 不足k个节点
            b = b.next;
        }
        
        // 反转前k个节点
        ListNode newHead = reverse(a, b);
        
        // 递归反转后续节点
        a.next = reverseKGroup(b, k);
        
        return newHead;
    }
    
    // 反转[a, b)区间的节点
    private ListNode reverse(ListNode a, ListNode b) {
        ListNode prev = null, curr = a;
        
        while (curr != b) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

6. 性能优化技巧

6.1 迭代法优化版本

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 边界检查
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = null;
        ListNode curr = head;
        
        // 使用do-while减少一次判断
        do {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        } while (curr != null);
        
        return prev;
    }
}

6.2 内存优化考虑

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = null;
        
        // 直接使用head作为curr，减少变量声明
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        
        return prev;
    }
}

7. 实际应用场景

7.1 数据结构操作

• 链表重组： 在实现复杂数据结构时需要动态调整链表结构
• 缓存淘汰： LRU缓存中需要将访问的节点移到链表头部

7.2 算法竞赛

• 基础操作： 反转链表是很多复杂链表算法的基础
• 组合应用： 与其他算法结合解决复杂问题

7.3 系统设计

• 数据流处理： 在流式数据处理中可能需要反转数据顺序
• 状态回滚： 在需要撤销操作的系统中使用

8. 常见错误与调试

8.1 常见错误

1. 忘记保存next指针： 导致链表断裂
2. 边界条件处理不当： 空链表或单节点链表
3. 递归栈溢出： 链表过长时递归深度过大

8.2 调试技巧

public class DebugHelper {
    // 可视化链表状态
    public static void printListState(ListNode prev, ListNode curr, ListNode next) {
        System.out.print("prev: " + (prev == null ? "null" : prev.val));
        System.out.print(", curr: " + (curr == null ? "null" : curr.val));
        System.out.println(", next: " + (next == null ? "null" : next.val));
    }
    
    // 检查链表完整性
    public static boolean isValidList(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;
        
        while (curr != null) {
            if (visited.contains(curr)) {
                System.out.println("检测到环形链表！");
                return false;
            }
            visited.add(curr);
            curr = curr.next;
        }
        
        return true;
    }
}

9. 总结

9.1 核心要点

1. 迭代法是最优解： 时间O(n)，空间O(1)
2. 三指针技巧： prev、curr、next的协调使用
3. 边界条件： 空链表和单节点链表的特殊处理
4. 递归思想： 理解递归的回溯过程

9.2 学习建议

1. 掌握基础： 先熟练掌握迭代法
2. 理解递归： 深入理解递归的执行过程
3. 练习变种： 通过变种问题加深理解
4. 注重细节： 关注边界条件和错误处理

9.3 进阶方向

• 双向链表的反转
• 循环链表的处理
• 多线程环境下的链表操作
• 链表与其他数据结构的结合应用

反转链表虽然是基础算法，但其中蕴含的指针操作技巧和递归思想是掌握更复杂链表算法的基础。通过深入理解和大量练习，可以为后续的算法学习打下坚实基础。