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日

相关文章

  • [EasyUI美化换肤]更换EasyUi图标

    [EasyUI美化换肤]更换EasyUi图标 EasyUI是一款非常实用的前端UI框架,拥有众多的组件和丰富的样式,但是默认的图标比较单一,不够美观,本篇文章将介绍如何对EasyUI的图标进行自定义更换的操作。 准备工作 在进行EasyUI图标的自定义更换前,我们需要先准备好两份文件: easyui.css文件:EasyUI的主CSS文件,用于设置EasyU…

    其他 2023年3月28日
    00
  • 重返德军总部:旧血脉无法进入游戏怎么办_快速解决方法介绍

    重返德军总部:旧血脉无法进入游戏怎么办 如果在玩重返德军总部:旧血脉的过程中,出现无法进入游戏的情况,可以按照以下方法快速解决: 1. 检查游戏配置要求 首先,检查一下自己的电脑是否符合游戏的配置要求: 操作系统:Windows 7和以上版本 处理器:英特尔i5-4590或相当处理器 内存:8 GB RAM 显卡:NVIDIA GTX 970或AMD 290…

    other 2023年6月27日
    00
  • 多元回归模型f检验的步骤

    多元回归模型F检验的步骤 多元回归模型的F检验是检验整个模型是否具有统计显著性的重要方法之一,它可以告诉我们回归方程是否能够较好地解释变量之间的关系。在进行F检验之前,我们需要先建立多元回归模型和进行有关变量的参数估计。以下是多元回归模型F检验的步骤。 步骤一:假设检验 在进行F检验前,需要设立假设检验,以下是我们需要进行的假设检验: 零假设 H0: 整个多…

    其他 2023年3月28日
    00
  • bootstrap日历插件datetimepicker使用方法

    Bootstrap日历插件datetimepicker使用方法攻略 介绍 Bootstrap日历插件datetimepicker是一个强大的日期和时间选择器,它基于Bootstrap框架,提供了丰富的功能和灵活的配置选项。本攻略将详细介绍datetimepicker的使用方法,并提供两个示例说明。 步骤 步骤1:引入必要的文件 首先,你需要在你的HTML文件…

    other 2023年9月6日
    00
  • ffplay常用命令

    ffplay常用命令 ffplay是FFmpeg项目中的一个简单的多媒体播放器,支持大多数视频和音频格式,具有丰富的功能和灵活的参数设置。在FFmpeg的安装目录下,可以找到ffplay的可执行文件。 以下是一些常用的ffplay命令和参数: 基本操作 播放文件 ffplay [filename] 将会打开一个窗口播放指定的媒体文件。 暂停/继续播放 在播放…

    其他 2023年3月28日
    00
  • js链表操作(实例讲解)

    js链表操作(实例讲解) 什么是链表 链表是一种基础数据结构,它由许多节点(Node)组成,每个节点都包含一个数据部分和一个指向下一个节点的指针。 链表可以看做是由多个节点组成的数据结构,每个节点包含元素值和指向下一个节点的指针属性。并且,链表可以表示各种抽象数据类型。链表中的第一个节点称为头节点。如果链表为空,则头节点为null。最后一个节点称为尾节点。尾…

    other 2023年6月27日
    00
  • python怎样图形编程

    那我来为您详细讲解Python图形编程的完整攻略。 一、概述 Python图形编程主要使用的是Python中的GUI(Graphical User Interface)库,因此熟悉Python语言的开发者可以直接通过GUI库来实现图形编程。Python中主要的GUI库有:Tkinter、wxPython、PyQt、PySide等。本文以Tkinter库为例,…

    其他 2023年4月16日
    00
  • 魔兽世界7.0武器战怎么输出 7种输出手法分析

    魔兽世界7.0武器战怎么输出 7种输出手法分析 作为一名魔兽世界的武器战士,在团队中输出高是非常重要的。下面,我们将介绍7种输出手法,帮助你提高武器战的输出能力。 1. 完美汲取 完美汲取可以大大提高武器战士的爆发输出。建议在使用该技能前保证怒气值至少为100。在目标血量较小时,使用斩杀技能,否则使用隆盛之力加强普通攻击。 2. 边缘之怒 边缘之怒可以提高武…

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