leetcode 中翻转链表用python怎么实现？

<think>嗯，用户想了解如何在LeetCode上用Python实现链表的翻转。首先，我得回忆一下链表翻转的基本思路。翻转链表通常有两种方法：迭代和递归。我应该先考虑用户可能的水平，如果是刚开始刷题的话，可能更倾向于迭代法，因为递归可能稍微难理解一些。 首先，我需要确认用户是否了解链表的结构。在Python中，链表通常由节点构成，每个节点包含值和指向下一个节点的指针。比如，定义一个ListNode类，有val和next两个属性。翻转链表的关键在于改变每个节点的next指针指向它的前一个节点。 那迭代法的话，需要三个指针吗？prev、current和next_temp。初始化时prev是None，current是头节点。然后循环，保存current的下一个节点next_temp，把current的next指向prev，然后prev移动到current，current移动到next_temp。直到current为空，这时候prev就是新的头节点。 然后是递归法。递归可能比较难，但代码简洁。递归到链表的末尾，然后从后往前翻转每个节点的指向。每次递归返回的是新的头节点，然后在回溯的过程中把当前节点的下一个节点的next指向自己，自己的next置为None。不过需要注意终止条件，当当前节点或下一个节点为空时返回。 接下来，可能需要考虑边界情况，比如空链表或者只有一个节点的链表，这时候直接返回头节点即可。测试用例的话，比如1->2->3->4->5翻转后应该是5->4->3->2->1。 用户可能希望看到具体的代码示例。所以应该给出两种方法的代码，并解释每一步的作用。比如迭代法的代码步骤，递归法的分解步骤。 另外，Python中链表的实现可能需要用户自己定义ListNode类，所以在代码示例中应该先给出这个定义，再写翻转函数。这样用户可以直接复制代码运行测试。 还要注意代码的可读性，变量命名要清晰，比如prev、curr、next_temp这样的名称。递归法中的终止条件和递归步骤的注释也很重要，帮助用户理解。 可能用户遇到的常见问题包括：指针操作顺序错误，比如没有先保存下一个节点就直接修改了current的next，导致链表断裂。或者在递归中没有正确处理next指针，导致循环链表或者未完全翻转。 总结下来，我应该分步骤解释两种方法，给出代码示例，并说明时间和空间复杂度。迭代法是O(n)时间，O(1)空间；递归法是O(n)时间，O(n)栈空间。这样用户可以根据需求选择适合的方法。 可能用户的实际应用场景是在LeetCode上解决类似问题，比如题目206. Reverse Linked List。所以直接针对该题给出解决方案会比较有用。另外，可能用户需要理解算法原理而不仅仅是代码，所以需要解释每一步的逻辑。 最后，检查是否有遗漏的情况，比如头节点处理，或者翻转后的链表是否正确连接。确保代码的正确性，避免死循环或者空指针错误。在</think> LeetCode 中翻转链表（Reverse Linked List）是一个经典问题（题目编号 [206](https://leetcode.com/problems/reverse-linked-list/)），以下是使用 Python 实现的两种常见方法：**迭代法**和**递归法**。假设链表的节点定义为： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` --- ### 方法一：迭代法 **核心思想**：通过遍历链表，逐步修改每个节点的指针方向。 #### 步骤： 1. 初始化三个指针：`prev`（前驱节点，初始为 `None`）、`curr`（当前节点，初始为头节点 `head`）。 2. 遍历链表，每次将当前节点的 `next` 指向 `prev`。 3. 更新 `prev` 和 `curr`，直到链表末尾。 #### 代码实现： ```python def reverseList(head: ListNode) -> ListNode: prev = None curr = head while curr: next_temp = curr.next # 保存下一个节点 curr.next = prev # 反转指针方向 prev = curr # prev 前进 curr = next_temp # curr 前进 return prev # 最后 prev 是新的头节点 ``` --- ### 方法二：递归法 **核心思想**：从链表的末尾开始反向修改指针，通过递归回溯实现翻转。 #### 步骤： 1. 递归到链表的最后一个节点，将其作为新头节点。 2. 在回溯过程中，将当前节点的下一个节点的 `next` 指向自己。 3. 将当前节点的 `next` 置为 `None`（避免循环）。 #### 代码实现： ```python def reverseList(head: ListNode) -> ListNode: if not head or not head.next: return head # 终止条件：空链表或最后一个节点 new_head = reverseList(head.next) # 递归到末尾 head.next.next = head # 反转指针方向 head.next = None # 避免循环 return new_head ``` --- ### 复杂度分析 | 方法 | 时间复杂度 | 空间复杂度 | |--------|------------|------------| | 迭代法 | O(n) | O(1) | | 递归法 | O(n) | O(n) | --- ### 示例 假设输入链表为 `1 -> 2 -> 3 -> 4 -> 5`，两种方法均会输出 `5 -> 4 -> 3 -> 2 -> 1`。 --- ### 关键点 1. **迭代法**需要维护 `prev` 和 `curr` 指针，逐步反转方向。 2. **递归法**需理解递归栈的回溯过程，确保正确修改指针。 如果有其他问题，欢迎继续提问！