LeetCode 206. Reverse Linked List

问题描述

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

解题思路

本题使用递归方式反转链表，核心思想是利用函数调用栈天然的后进先出特性。

递归三部曲

1. 终止条件：当链表为空 (head == null) 或只有一个节点 (head.next == null) 时，直接返回 head，因为空链表或单节点链表反转后仍是自身。

2. 递推过程：递归调用 reverseList(head.next)，一直深入到链表的最后一个节点。当递归触底时，返回的 newHead 就是原链表的尾节点，也就是反转后链表的头节点。

3. 回溯处理：当递归逐层返回时，假设当前节点为 head，其下一个节点 head.next 已经完成了它之后所有节点的反转。此时 head.next 指向的是反转后链表中的最后一个节点（即原链表中 head 之后的子链表反转后的尾节点）。我们需要做两件事：

   • 将 head.next.next = head，让原本指向 head 的节点反过来指向 head
   • 将 head.next = null，断开 head 对后续节点的引用，防止形成环

举例说明

以链表 1 -> 2 -> 3 -> 4 -> 5 为例：

• 递归深入到节点 5，5.next == null，返回 5 作为 newHead
• 回溯到节点 4：4.next.next = 4（即 5.next = 4），4.next = null，得到 5 -> 4
• 回溯到节点 3：3.next.next = 3（即 4.next = 3），3.next = null，得到 5 -> 4 -> 3
• 依此类推，最终得到 5 -> 4 -> 3 -> 2 -> 1

复杂度分析

• 时间复杂度：O(n)，需要遍历链表中的每个节点一次。
• 空间复杂度：O(n)，递归调用栈的深度为链表长度 n。

代码

package code.J206;

import datastructure.ListNode;

public class J206 {
    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;
    }
}