【LeetCode】206. 反转链表

in #programming3 months ago

1 题目描述

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

2 解题思路

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

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 方法处理下一个节点。