本文共 1143 字，大约阅读时间需要 3 分钟。

反转链表并提取节点值是一个常见的链表操作问题。以下是一个基于代码示例的详细解释和优化版本：

问题描述

给定一个单链表的头节点，要求从尾部到头部反转链表，并返回每个节点的值作为一个数组。

示例

输入：head = [1,3,2]输出：[2,3,1]

代码逻辑解释

代码采用了递归的方法来实现链表的反转。具体步骤如下：

代码优化措施

• 去掉不必要的空格和格式字符：确保代码格式简洁，不影响可读性。
• 避免使用复杂结构：使用简单的逻辑表达，避免采用过于复杂的数据结构或语法。

逐步代码解释

class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass Solution:    def reversePrint(self, head: ListNode) -> List[int]:        res = self.getValue(head)        return res    def getValue(self, head: ListNode) -> List[int]:        if head is None:            return []        else:            res = self.getValue(head.next)  # 递归处理下一个节点            res.append(head.val)  # 将当前节点的值添加到结果数组最后            return res

工作流程举例

假设初始链表为：1 -> 3 -> 2 -> None

• 递归第一个调用：getValue(1)
  • 调用 getValue(3)
    • 调用 getValue(2)
      • 调用 getValue(None): 返回空数组 []
      • res = []，append(2): 返回 [2]
    • res = [2], append(3): 返回 [2,3]
  • res = [2,3], append(1): 返回 [2,3,1]

最终输出结果为 [2,3,1]，与题目要求一致。

代码性能分析

该算法的时间复杂度为 O(n)，因为我们只需要遍历链表一次。在最坏情况下（链表长度为 10000），该算法仍能高效运行。

这种递归方法虽然简洁，但在极端情况下可能会导致栈溢出。可以通过迭代的方式来优化代码，但递归实现更直观且易于理解。

转载地址：http://fggcz.baihongyu.com/