python算法题 链表反转详解
作者:FOOFISH-PYTHON之禅 时间:2021-01-26 11:47:35
链表的反转是一个很常见、很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表。实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归。
第一种方式:循坏迭代
循坏迭代算法需要三个临时变量: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
标签:python,算法,链表,反转
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
详解重置Django migration的常见方式
2022-10-30 13:21:17
DHTML实例解析:用HTC统一定制表单样式
2007-11-04 18:48:00
ASP初学者常犯的几个错误
2007-09-07 10:19:00
![](https://img.aspxhome.com/file/UploadPic/2007-1/2007130163317843s.gif)
Javascript调用XML制作连动下拉框
2007-09-17 12:55:00
ORACLE 常用函数总结(80个)第1/2页
2009-09-18 13:23:00
一个简单的鼠标划过切换效果js源码
2010-06-21 10:55:00
![](https://img.aspxhome.com/file/UploadPic/20106/21/100523-64s.jpg)
Python将多个excel表格合并为一个表格
2021-10-18 22:50:22
![](https://img.aspxhome.com/file/2023/8/81818_0s.jpg)
Django contenttypes 框架详解(小结)
2023-11-13 14:39:47
![](https://img.aspxhome.com/file/2023/0/90910_0s.png)
动态载入树 (ASP+数据库)
2010-05-27 12:20:00
基于Python实现微信聊天界面生成器
2021-12-19 20:36:02
![](https://img.aspxhome.com/file/2023/6/67906_0s.png)
Mootools 1.2教程(7)——设置和获取样式表属性
2008-11-25 13:48:00
PHP数组交集的优化代码分析
2023-09-29 21:58:59
js自动闭合html标签(自动补全html标记)
2023-08-25 07:06:35
SQL Server 2005返回刚刚插入的数据条目id值
2008-12-04 17:16:00
asp Server对象之MapPath方法
2010-07-07 12:28:00
Oracle数据库3种关闭方式
2008-06-13 16:46:00
让MYSQL彻底支持中文
2008-12-24 16:23:00
Python常见数据结构详解
2021-10-28 22:07:33
Python requests发送post请求的一些疑点
2022-09-09 17:45:03
![](https://img.aspxhome.com/file/2023/9/77609_0s.png)
python的concat等多种用法详解
2022-08-14 23:37:18