ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何在 Python 中使用递归反转链表？

如何在 Python 中使用递归反转链表？

原创 Python 作者：mingtian66 时间：2024-11-12 16:04:03 0 删除 编辑

在 Python 中可以通过递归的方法反转链表。以下是实现步骤：

假设我们有一个单链表，每个节点包含一个值 val 和指向下一个节点的 next 指针。我们将定义一个节点的类 ListNode，并实现递归函数来反转链表。
节点类定义

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

递归反转链表的函数

递归的思想是：我们可以反转链表的子部分，直到只剩下一个节点（或没有节点）。然后，逐步将每个节点的 next 指针指向其前一个节点，最终完成整个链表的反转。

def reverse_list(head):
    # 递归终止条件：如果链表为空或只有一个节点，直接返回该节点
    if not head or not head.next:
        return head
    
    # 递归反转剩下的链表
    new_head = reverse_list(head.next)
    
    # 将当前节点的下一个节点的 next 指向当前节点
    head.next.next = head
    
    # 当前节点的 next 设为 None，以防形成环
    head.next = None
    
    return new_head

示例用法

我们可以创建一个链表并调用 reverse_list 函数来测试：

# 创建一个链表 1 -> 2 -> 3 -> 4 -> 5 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 反转链表
reversed_head = reverse_list(head)

# 打印反转后的链表
current = reversed_head
while current:
    print(current.val, end=" -> ")
    current = current.next
# 输出：5 -> 4 -> 3 -> 2 -> 1 -> None

代码说明

    递归终止条件：当 head 为 None 或 head.next 为 None 时，说明链表为空或只有一个节点，直接返回 head。
    递归反转子链表：调用 reverse_list(head.next) 以反转从 head.next 开始的链表。
    调整指针方向：将 head.next.next 指向 head，相当于把当前节点 head 放到反转后的子链表的末尾。
    断开当前节点的 next：将 head.next 设为 None，避免形成环。
    返回新头节点：递归的返回值 new_head 是反转后的链表的头节点，最终返回给调用者。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048501/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 如何在 Python 中实现斐波那契数列的动态规划版本？
下一篇： java中为什么不能在构造器中调用 super() 抛出异常？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603019

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593