在数据结构中，单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的反转是一个经典的算法问题，掌握它对于理解链表操作和递归思想非常有帮助。本文将详细介绍如何在Python中实现单链表的反转，并提供两种常见的实现方法：迭代法和递归法。
在开始反转单链表之前，我们首先需要定义单链表的基本结构。一个单链表节点通常包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 在这个定义中，ListNode类表示单链表的一个节点。val是节点的数据，next是指向下一个节点的指针。
迭代法是一种通过循环来逐步反转链表的方法。其基本思想是使用三个指针：prev、curr和next。prev指向当前节点的前一个节点，curr指向当前节点，next指向当前节点的下一个节点。通过不断更新这三个指针，我们可以逐步将链表反转。
prev为None，curr为链表的头节点。curr为None： curr的下一个节点到next。curr的next指针指向prev。prev移动到curr。curr移动到next。prev将指向反转后的链表的头节点。def reverseList(head: ListNode) -> ListNode: prev = None curr = head while curr: next_node = curr.next # 保存下一个节点 curr.next = prev # 反转当前节点的指针 prev = curr # 移动prev到当前节点 curr = next_node # 移动curr到下一个节点 return prev # prev现在是新的头节点 假设我们有一个单链表：1 -> 2 -> 3 -> 4 -> 5，使用迭代法反转后，链表将变为：5 -> 4 -> 3 -> 2 -> 1。
递归法是另一种反转单链表的方法。其基本思想是将链表分为头节点和剩余部分，递归地反转剩余部分，然后将头节点连接到反转后的剩余部分的末尾。
next指针指向当前节点。next指针指向None。def reverseListRecursive(head: ListNode) -> ListNode: # 递归终止条件 if not head or not head.next: return head # 递归反转剩余部分 new_head = reverseListRecursive(head.next) # 将当前节点的下一个节点的next指针指向当前节点 head.next.next = head # 将当前节点的next指针指向None head.next = None return new_head 同样以链表1 -> 2 -> 3 -> 4 -> 5为例，使用递归法反转后，链表将变为：5 -> 4 -> 3 -> 2 -> 1。
单链表的反转是一个基础但重要的算法问题。通过迭代法和递归法，我们可以有效地反转单链表。迭代法适合处理较长的链表，而递归法则代码简洁，但在处理非常长的链表时需要注意栈溢出的问题。掌握这两种方法，可以帮助我们更好地理解链表操作和递归思想。
在实际应用中，选择哪种方法取决于具体的需求和场景。希望本文的介绍能够帮助你更好地理解和掌握单链表的反转操作。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
