反转列表(不确定我的递归方式算不算作弊呀～)
来源：4-10 算法与数据结构练习题：反转链表
石小咚丶
2022-11-28
循环方式
from typing import Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
result = None
last_node = None
cur_node = head
while cur_node:
next_node = cur_node.next
cur_node.next = last_node
last_node = cur_node
if next_node is None:
result = cur_node
cur_node = next_node
return result
递归方式
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode], result=None) -> Optional[ListNode]:
if head is None:
return result
cur_node = ListNode(head.val, next=result)
return self.reverseList(head.next, cur_node)
1回答
-
好帮手慕小李
2025-02-13
在编程中，并没有绝对的“作弊”行为，关键是你的解决方案是否满足题目的要求，并且是否高效。递归和循环都是解决链表反转问题的有效方法，它们各有优缺点。
递归方式：递归方法通常更简洁，代码量更少，易于理解和实现。但是，递归方法可能会因为深度递归导致栈溢出（stack overflow），尤其是在处理非常长的链表时。此外，递归方法可能会使用更多的内存，因为它需要在调用栈上保存多个函数调用的状态。
循环方式：循环方法通常更稳定，因为它不会受到递归深度的限制。它通常使用更少的内存，因为它不需要在调用栈上保存多个函数调用的状态。但是，循环方法可能需要更多的代码，并且可能不如递归方法那样直观。
你的递归实现：你的递归实现有一个小问题，即你在递归调用中创建了一个新的
ListNode对象，这会导致内存使用增加，并且不是原地（in-place）修改链表。正确的递归实现应该直接修改原链表的next指针，而不是创建新的节点。以下是正确的递归实现：Python复制
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: if head is None or head.next is None: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head
在这个实现中，我们递归地反转链表，直到到达链表的末尾（即
head.next为None）。然后，我们修改next指针来反转链表，最后返回新的头节点new_head。总结：
递归和循环都是解决链表反转问题的有效方法。
递归方法更简洁，但可能会受到递归深度的限制，并且可能使用更多的内存。
循环方法更稳定，使用更少的内存，但可能需要更多的代码。
在LeetCode上，重要的是你的解决方案是否满足题目的要求，并且是否高效。如果你的递归实现能够正确反转链表并且没有超时或内存溢出的问题，那么它就是一个有效的解决方案。
00
相似问题