LCR 024. 反转链表

1、迭代

这段代码是一个用于反转单链表的Java类。下面是对代码的详细解释：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // 初始化前一个节点为null，因为反转后链表的最后一个节点的next应该是null
        ListNode curr = head; // 当前节点初始化为链表的头节点
        while (curr != null) { // 当当前节点不为null时，继续循环
            ListNode next = curr.next; // 保存当前节点的下一个节点
            curr.next = prev; // 将当前节点的next指向前一个节点，实现反转
            prev = curr; // 前一个节点更新为当前节点
            curr = next; // 当前节点更新为下一个节点
        }
        return prev; // 当循环结束时，prev指向新的链表头节点，返回prev
    }
}

代码逻辑解释：

1. 初始化：

   • prev 初始化为 null，因为反转后链表的最后一个节点的 next 应该是 null。
   • curr 初始化为 head，即链表的头节点。

2. 循环：

   • 当 curr 不为 null 时，继续循环。
   • 在循环内部：
     • next 保存 curr 的下一个节点。
     • curr.next 指向 prev，实现当前节点的反转。
     • prev 更新为 curr，即前一个节点更新为当前节点。
     • curr 更新为 next，即当前节点更新为下一个节点。

3. 返回：

   • 当循环结束时，prev 指向新的链表头节点，返回 prev。

示例：

假设链表为 1 -> 2 -> 3 -> 4 -> 5，经过上述代码处理后，链表将变为 5 -> 4 -> 3 -> 2 -> 1。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表的长度。每个节点都被访问一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

递归

这段代码是一个递归实现的单链表反转函数。下面是对代码的详细解释：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // 反转当前节点的下一个节点的next指针
        head.next = null; // 确保当前节点的next指针为null，避免产生环
        return newHead;
    }
}

代码逻辑解释：

1. 基本情况：

   • 如果链表为空（head == null）或者链表只有一个节点（head.next == null），直接返回 head。因为空链表或单个节点的链表反转后仍然是它本身。

2. 递归调用：

   • 递归调用 reverseList(head.next)，反转从第二个节点开始的剩余链表部分。递归调用会一直进行，直到链表的末尾（基本情况）。

3. 反转操作：

   • 当递归调用返回时，newHead 是反转后链表的新头节点（即原链表的最后一个节点）。
   • head.next.next = head：将当前节点的下一个节点的 next 指针指向当前节点，实现反转。
   • head.next = null：将当前节点的 next 指针置为 null，断开原来的连接，确保链表的尾部正确。

4. 返回新的头节点：

   • 返回 newHead，即反转后链表的新头节点。
     注意⚠️：
     反转链表的过程中，确保反转后的链表的尾部指向 null 是至关重要的，否则链表中可能会产生环，导致无限循环或其他错误。

假设我们有一个链表 1 -> 2 -> 3 -> 4 -> 5，我们希望将其反转成 5 -> 4 -> 3 -> 2 -> 1。

在递归反转的过程中，当我们处理到节点 1 时，head 指向 1，而 head.next 指向 2。在反转操作中，我们需要将 2 的 next 指针指向 1，即 head.next.next = head。但是，如果我们不将 head.next 置为 null，那么 1 的 next 指针仍然指向 2，这样就会形成一个环 1 -> 2 -> 1，导致链表中产生环。

因此，在反转操作之后，我们必须显式地将 head.next 置为 null，以确保链表的尾部正确地指向 null，避免产生环。

示例：

假设链表为 1 -> 2 -> 3 -> 4 -> 5，经过上述代码处理后，链表将变为 5 -> 4 -> 3 -> 2 -> 1。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是链表的长度。每个节点都被访问一次。
• 空间复杂度：O(n)，递归调用栈的深度最多为 n。