反转链表-递归-代码-示例

代码实现

import java.util.*;

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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

第一次递归调用

调用 ReverseList(head)，其中 head 是指向第一个节点 1 的指针。

第二次递归调用

进入第一次递归调用，继续调用 ReverseList(head.next)，其中 head.next 是指向第二个节点 2 的指针。

第三次递归调用

进入第二次递归调用，继续调用 ReverseList(head.next)，其中 head.next 是指向第三个节点 3 的指针。

第四次递归调用

进入第三次递归调用，继续调用 ReverseList(head.next)，其中 head.next 是指向第四个节点 4 的指针。

递归基准条件

在第四次递归调用中，head 为 4，触发递归基准条件，直接返回当前节点 4 作为新的头节点 newHead。

递归回溯

在递归回溯的过程中，对每个节点执行以下操作：

head.next.next = head;
head.next = null;

以节点 3 为例，执行后的链表状态如下：

1 -> 2 -> 3 <- 4

对节点 2 和 1 分别执行相同的操作，得到：

1 <- 2 <- 3 <- 4

返回结果

最终，newHead 指向反转后的链表的头节点，即节点 4。整个链表变为：

4 -> 3 -> 2 -> 1

注意事项

• 在使用递归时，请确保链表不会太长，以免导致栈溢出。对于极长的链表，可能需要考虑使用迭代方法。
• 确保链表节点的定义与提供的 ListNode 类一致，包含一个整数值 val 和一个指向下一个节点的指针 next。
• 在实际应用中，可以根据具体需求进行适当的修改和优化，确保代码符合项目的整体结构和规范。

希望这一篇文档能够帮助您理解链表反转的代码实现和执行过程。如果您有其他疑问，请随时提出。