python递归&迭代方法实现链表反转

接下来我将详细讲解如何使用Python的递归和迭代方法实现链表的反转。

什么是链表反转

链表反转(reverse a linked list)指的是将链表中的所有节点的指针方向都倒转,即原来指向下一个节点的指针变为指向前一个节点,这样可以让链表的尾部变为头部,实现链表的逆序。

实现方法

链表反转可以使用递归和迭代两种方法进行实现。

递归方法

递归反转链表的思路是:

  • 递归到链表的最后一个节点;
  • 从最后一个节点开始,将每个节点的下一个节点的指针指向自己;
  • 返回反转后的链表头节点。

用Python代码实现递归反转链表:

# 定义节点结构
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 递归反转链表
def reverseList(head):
    if not head or not head.next:
        return head
    newHead = reverseList(head.next)
    head.next.next = head
    head.next = None
    return newHead

使用以下代码进行测试:

# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 打印反转前的链表
p = node1
while p:
    print(p.val, end=" ")
    p = p.next
print()

# 反转链表
newHead = reverseList(node1)

# 打印反转后的链表
p = newHead
while p:
    print(p.val, end=" ")
    p = p.next
print()

输出结果如下:

1 2 3 4 5 
5 4 3 2 1 

迭代方法

迭代反转链表的思路是:

  • 使用三个指针分别指向当前节点、前一个节点和后一个节点;
  • 当前节点指向前一个节点,然后三个指针依次向后移动一个节点;
  • 返回反转后的链表头节点。

用Python代码实现迭代反转链表:

# 迭代反转链表
def reverseList(head):
    if not head or not head.next:
        return head
    pre = None
    cur = head
    nxt = head.next
    while cur:
        cur.next = pre
        pre = cur
        cur = nxt
        nxt = nxt.next if nxt else None
    return pre

使用以下代码进行测试:

# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 打印反转前的链表
p = node1
while p:
    print(p.val, end=" ")
    p = p.next
print()

# 反转链表
newHead = reverseList(node1)

# 打印反转后的链表
p = newHead
while p:
    print(p.val, end=" ")
    p = p.next
print()

输出结果如下:

1 2 3 4 5 
5 4 3 2 1 

总结

递归和迭代是两种常见的解决链表反转问题的方法。对于链表较长的情况下,使用迭代方法需要额外的空间来保存三个指针,因此递归方法更节省空间。但是在Python中,递归深度有限制,因此对于较长的链表还是推荐使用迭代方法来实现反转。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python递归&迭代方法实现链表反转 - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • win11本地帐号名称怎么更改? win11修改本地账户名称的技巧

    以下是win11本地账户名称修改的攻略: 1. 打开控制面板 首先,进入windows 11系统的控制面板。在搜索框中输入“控制面板”,然后点击打开。 2. 选择“用户帐户” 在控制面板中,选择“用户帐户”,然后选择“更改帐户类型”。 3. 选择要更改的本地账户 在“更改帐户类型”界面中,选择需要更改名称的本地账户。点击账户名称旁边的“更改帐户名称”按钮。 …

    other 2023年6月27日
    00
  • Mac OS中设置环境变量的教程

    下面是 Mac OS 中设置环境变量的完整攻略,包含以下步骤: 1. 打开终端 在 Mac OS 中,环境变量的设置需要通过终端来完成。打开终端的方式是在 Spotlight 中搜索“终端”,或者在 Finder 中进入应用程序 -> 实用工具,找到“终端”并打开。 2. 查看当前环境变量 在终端中输入以下命令,查看当前系统中已经存在的环境变量: pr…

    other 2023年6月27日
    00
  • 解决win7系统打开程序提示不是有效的win32应用程序问题

    下面是解决win7系统打开程序提示不是有效的win32应用程序问题的完整攻略: 问题背景 在使用win7系统时,有时会遇到一些程序打开时提示“不是有效的Win32应用程序”的问题。这个问题可能是由多种原因引起的,例如: 应用程序的完整性检查(Digital Signature)不正确 应用程序被病毒感染 应用程序与操作系统不兼容 无论是何种原因,这个问题都会…

    other 2023年6月25日
    00
  • Python中类的定义、继承及使用对象实例详解

    下面是关于Python中类的定义、继承及使用对象实例的完整攻略: 类的定义 在Python中,通过class关键字来定义一个类。类的定义通常包含类的属性和方法。在类中定义方法时,默认第一个参数是self,代表该方法所属的实例对象。实例对象的属性可以通过self来定义和引用。 以下是一个定义Person类的示例: class Person(object): d…

    other 2023年6月26日
    00
  • androideasybarrage实现轻量级弹幕效果

    AndroidEasyBarrage实现轻量级弹幕效果 AndroidEasyBarrage是一款轻量级的弹幕效果库,它可以帮助开发者快速实现弹幕效果。在本文中,我们将详细讲解AndroidEasyBarrage使用方法,包括两个示例说明。 步骤 添加依赖 在使用AndroidEasyBarrage之前,需要在项目中添加依赖。可以在项目的build.grad…

    other 2023年5月8日
    00
  • ffmpeg批量转吗

    ffmpeg批量转码 在日常的视频处理和编辑过程中,我们经常需要将一些视频文件转换成特定的格式或者特定的参数,以满足特定的需求。常见的转换工具之一就是FFmpeg。这个工具本身提供了很多命令行选项,可以进行转码、剪辑、过滤等操作。但是,如果我们需要对很多视频文件进行相同的操作,手工一个一个进行命令行处理就非常繁琐费时。本文将介绍如何使用FFmpeg进行批量转…

    其他 2023年3月28日
    00
  • C++共享内存删除的陷阱

    C++共享内存删除的陷阱攻略 在C++中,使用共享内存可以实现进程间的数据共享。然而,共享内存的删除过程中存在一些陷阱,需要特别注意。本攻略将详细讲解这些陷阱,并提供两个示例说明。 1. 共享内存的创建和删除 在开始讲解陷阱之前,我们先回顾一下共享内存的创建和删除过程。 创建共享内存 创建共享内存的过程通常包括以下几个步骤: 使用shmget函数创建一个共享…

    other 2023年8月1日
    00
  • 微信小程序(四)应用生命周期详解

    我来为您详细讲解一下“微信小程序(四)应用生命周期详解”的完整攻略。 应用生命周期 程序启动 当用户首次打开小程序时,触发onLaunch事件,进行初始化操作,例如获取用户信息、提前获取需要缓存的数据等。 App({ globalData: { userInfo: null, someData: null }, onLaunch: function () {…

    other 2023年6月27日
    00
合作推广
合作推广
分享本页
返回顶部