1 题目描述

206. 反转链表要求给定单链表的头节点 head，任务是反转链表，并返回反转后的链表。

2 解题思路

1. 递归反转：使用递归方法，每次反转当前节点 cur 的 next 指针，使其指向其前一个节点 prev。
2. 终止条件：当 cur 指针为空时，递归结束，此时 prev 指针即为反转后链表的头节点。
3. 更新指针：每次递归调用返回后，更新 cur 和 prev 的值，以便进行下一次反转操作。

3 Java 代码实现

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 开始反转过程，初始时 prev 为 null
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode prev) {
        // 当 cur 为空时，反转完成
        if (cur == null)
            return prev;
        
        // 保存 cur 的下一个节点
        ListNode temp = cur.next;
        
        // 将 cur 的 next 指向 prev，完成一次反转
        cur.next = prev;
        
        // 递归地反转剩余的链表部分
        return reverse(temp, cur);
    }
}

• 时间复杂度: O(n)，其中 n 是链表中的节点数。每个节点恰好被访问一次。
• 空间复杂度: O(n)，这是由于递归栈需要 O(n) 的空间来保存每一次递归调用的信息。

4 注意事项

• 递归方法：使用递归方法来反转链表，这种方法简洁明了。
• 辅助方法：定义了一个辅助方法 reverse，它接受当前节点 cur 和前一个节点 prev 作为参数。
• 基线条件：当 cur 为空时，返回 prev 作为新的头节点。
• 递归调用：在递归调用中，先保存 cur.next，然后将 cur.next 指向 prev，再递归调用 reverse 方法处理下一个节点。