反转单向链表
在编程语言中，链表是一种常用的数据结构。单向链表是一种线性数据结构，其中每个元素包含数据和一个指向下一个元素的指针。在某些情况下，可能需要反转单向链表。在Python中，可以使用迭代或递归方法来实现此操作。
递归方法
递归是一种在函数内部调用自身的编程技术。使用递归方法反转单向链表的基本思想是将链表分成两部分，然后递归地反转每一部分，最后将它们连接起来。
pythonclass ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseList(head):
if head is None or head.next is None:
return head
else:
new_head = reverseList(head.next)
head.next.next = head
head.next = None
return new_head
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseList(head):
if head is None or head.next is None:
return head
else:
new_head = reverseList(head.next)
head.next.next = head
head.next = None
return new_head迭代方法
迭代方法是通过使用一个循环来反转链表。这种方法比递归方法更直观，因为它不需要处理额外的函数调用。
pythonclass ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseList(head):
prev = None
curr = head
while curr is not None:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseList(head):
prev = None
curr = head
while curr is not None:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev这两种方法都可以有效地反转单向链表。递归方法更简洁，但如果链表很长，可能会导致栈溢出。迭代方法则不会有这个问题，因此在实际使用中，应根据链表的长度和具体情况选择合适的方法。
