神剑山庄资源网

python算法题 链表反转详解
脚本专栏 2024/11/6 佚名
2 0
神剑山庄资源网 Design By www.hcban.com

链表的反转是一个很常见、很基础的数据结构题，输入一个单向链表，输出逆序反转后的链表，如图：上面的链表转换成下面的链表。实现链表反转有两种方式，一种是循环迭代，另外一种方式是递归。

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

python算法题 链表反转详解

第二种方式：递归

递归的思想就是：

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


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

标签：
python,算法题,链表反转
神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网 免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
神剑山庄资源网 Design By www.hcban.com

评论“python算法题 链表反转详解”

暂无python算法题 链表反转详解的评论...
www.hcban.com 神剑山庄资源网
139,976影音资源
144,792福利资源
21,817软件资源
631,128技术资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
神剑山庄资源网 Design By www.hcban.com