Python OJ题典型:链表反转的迭代和递归

简介: 本文介绍了如何使用迭代和递归两种方法来实现链表的反转。通过详细的解题思路和代码实现,帮助读者理解链表反转的原理和实现方式。

算法介绍

本文将介绍如何反转链表,即将原链表的头节点变为新链表的尾节点。我们将通过迭代和递归两种方式实现链表的反转。

算法解析

给定一个链表,我们需要实现一个函数来反转这个链表,并返回反转后的链表头节点。

解题思路

1. 迭代法

迭代法是最常见的解决链表反转的方法。我们可以使用三个指针,分别指向前一个节点、当前节点和下一个节点。通过不断更新指针的指向,将链表中的节点一个个反转。

具体步骤如下:

  1. 初始化指针 prevNone,指针 curr 为链表的头节点。
  2. 循环遍历链表,直到当前节点 curr 为空。
    1. 将当前节点的下一个节点保存为临时变量 next
    2. 将当前节点的 next 指向前一个节点 prev
    3. 更新指针 prev 为当前节点 curr
    4. 更新指针 curr 为临时变量 next
  3. 循环结束后,返回更新后的链表头节点 prev

2. 递归法

递归法是另一种实现链表反转的方法。递归的思想是将大问题分解为小问题的求解,直到达到基本情况。

具体步骤如下:

  1. 定义递归函数 reverseList,接收一个链表节点作为参数。
  2. 当前节点为空或者下一个节点为空时,直接返回当前节点。
  3. 递归调用 reverseList 函数,传入下一个节点,并将返回结果保存为变量 newHead
  4. 将下一个节点的 next 指向当前节点。
  5. 将当前节点的 next 设为 None
  6. 返回 newHead

代码实现

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseListIteratively(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

def reverseListRecursively(head):
    if not head or not head.next:
        return head

    new_head = reverseListRecursively(head.next)
    head.next.next = head
    head.next = None

    return new_head

# 测试示例
# 创建链表 1->2->3->4->5
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)

# 迭代法反转链表
iterative_result = reverseListIteratively(head)

# 递归法反转链表
recursive_result = reverseListRecursively(head)

解题技巧

  • 迭代法适用于链表反转问题,使用三个指针进行节点更新。
  • 递归法通过不断调用函数自身来解决链表反转问题,需要注意停止条件和指针的更新。

总结

本文介绍了两种方法来实现链表的反转:迭代法和递归法。迭代法通过使用三个指针来反转链表中的节点,而递归法则是通过不断调用函数自身来实现链表的反转。根据实际情况选择合适的方法来解决链表反转问题。

目录
相关文章
|
6天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
24 2
|
22天前
|
Python
【10月更文挑战第18天】「Mac上学Python 29」基础篇10 - 循环结构与迭代控制
在Python中,循环结构是控制程序执行的重要工具。通过学习本篇内容,您将掌握如何使用for循环和while循环来高效地处理重复任务,并了解break、continue和else的使用方式。同时,我们还会探索嵌套循环和典型应用场景中的实际应用。
37 2
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
25 7
|
1月前
|
Java 程序员 C++
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
23 0
【Python】链式、嵌套调用、递归、函数栈帧、参数默认值和关键字参数
|
2月前
|
Python
python之迭代
python之迭代
|
1月前
|
存储 大数据 数据处理
理解Python中的生成器:高效迭代的秘密
【10月更文挑战第8天】理解Python中的生成器:高效迭代的秘密
33 0
|
2月前
|
Python
Python中的zip:高效处理并行迭代的利器
Python中的zip:高效处理并行迭代的利器
23 0
|
3月前
|
算法 Python
python函数递归和生成器
python函数递归和生成器
|
3月前
|
算法 数据挖掘 Python
|
3月前
|
数据采集 Java Python
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器
python 递归锁、信号量、事件、线程队列、进程池和线程池、回调函数、定时器