python算法题 链表反转详解
作者:FOOFISH-PYTHON之禅 发布时间:2021-01-26 11:47:35
标签:python,算法,链表,反转
链表的反转是一个很常见、很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表。实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归。
第一种方式:循坏迭代
循坏迭代算法需要三个临时变量:pre、head、next,临界条件是链表为None或者链表就只有一个节点。
# encoding: utf-8
class Node(object):
def __init__(self):
self.value = None
self.next = None
def __str__(self):
return str(self.value)
def reverse_loop(head):
if not head or not head.next:
return head
pre = None
while head:
next = head.next # 缓存当前节点的向后指针,待下次迭代用
head.next = pre # 这一步是反转的关键,相当于把当前的向前指针作为当前节点的向后指针
pre = head # 作为下次迭代时的(当前节点的)向前指针
head = next # 作为下次迭代时的(当前)节点
return pre # 返回头指针,头指针就是迭代到最后一次时的head变量(赋值给了pre)
测试一下:
if __name__ == '__main__':
three = Node()
three.value = 3
two = Node()
two.value = 2
two.next = three
one = Node()
one.value = 1
one.next = two
head = Node()
head.value = 0
head.next = one
newhead = reverse_loop(head)
while newhead:
print(newhead.value, )
newhead = newhead.next
输出:
3
2
1
0
2
第二种方式:递归
递归的思想就是:
head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
...
head的向后指针的向后指针转换成head的向后指针,依此类推。
实现的关键步骤就是找到临界点,何时退出递归。当head.next为None时,说明已经是最后一个节点了,此时不再递归调用。
def reverse_recursion(head):
if not head or not head.next:
return head
new_head = reverse_recursion(head.next)
head.next.next = head
head.next = None
return new_head
来源:https://foofish.net/linklist-reverse.html
0
投稿
猜你喜欢
- 遇到一个难题,在无物理键盘情况下,通过页面软键盘在页面文本框输入汉字,不知道51js的各位大牛有没有遇到过这种需求,如果遇到过是如何解决的,
- 亮度调整非线性亮度调整:对于R,G,B三个通道,每个通道增加相同的增量。线性亮度调整:利用HSL颜色空间,通过只对其L(亮度)部分调整,可达
- 剑指Offer(Python多种思路实现):剪绳子面试14题:题目:剪绳子题:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,且n
- flask中的sqlalchemy 相比于sqlalchemy封装的更加彻底一些 , 在一些方法上更简单首先import类库:在CODE上查
- 前言:Python 是一种脚本语言,相比 C/C++ 这样的编译语言,在效率和性能方面存在一些不足。但是,有很多时候,Python 的效率并
- instanceof 运算符 和 is_a() 方法都是判断:某对象是否属于该类 或 该类是此对象的父类(用于确定一个 PHP 变量是否属于
- 本文实例为大家分享了python实现单机五子棋对战的具体代码,供大家参考,具体内容如下 引入pygame模块 # 1、引
- 导语:除夕除夕,就是除去烦脑,迎接新的希望!在这里小编先祝大家除夕快乐,岁岁常欢笑,事事皆如意!正文:创建画布setup和draw是p5.j
- 前言一些公司内部的CMS系统存在某些内容让指定的用户有权限访问,这时候可以用django自带的权限管理进行限制,比较方便。缺点:django
- 一 前言 问题的存在 从代码级别上,也就是应用层次上考虑代码安全的话(也就是不考虑底层的语言本身等问题的漏洞),脚本安全问题就是函数和变量的
- PHP number_format() 函数实例格式化数字:<?php echo number_format("100000
- 在我们关于SQL服务器安全系列的这文章里,我们的目标是向你提供安全安装SQL服务器所需要的工具和信心,这样的话,你有价值的数据就会受到保护,
- 实验室新装了keras,发现keras默认后端是tensorflow,想换回theano,看了官方文档也没搞懂,最终搞定,很简单。中文文档的
- 本文介绍,在 VSCode 使用 IPython Kernel的设置方法,详细介绍如下所示:要达到的效果:只需按下 Ctrl+;,选中的几行
- 其实也算不上教程,也就是自己没事儿的时候做点东西然后发上来大家交流交流,希望大家不吝赐教^!^因为刚看过亚东的教程和这个有点相似,所以就自己
- 一。首先,添加如下存储过程CREATE PROCEDURE dbo.ChangeObjectOwner @Ol
- 0x 00 返回值简介回顾下,上一节简单介绍了函数及其各种参数,其中也有简单介绍 print 和 return 的区别,print 仅仅是打
- 今年年初之时,微软发布了一个针对ActiveX控件的补丁,安装此补丁后的IE6中,当ActiveX控件获得焦点时,IE自动为其套上一个虚线矩
- 本文实例讲述了Python基于最小二乘法实现曲线拟合。分享给大家供大家参考,具体如下:这里不手动实现最小二乘,调用scipy库中实现好的相关
- 如何在网站上提供音乐下载?为用户提供歌曲下载,一般有两种方式,一是直接通过Http,浏览器下载,二是通过ftp协议下载。我们来用Http和浏