用python介绍4种常用的单链表翻转的方法小结
如何把一个单链表进行反转？
方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。
方法2：使用3个指针html" target="_blank">遍历单链表，逐个链接点进行反转。
方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。
方法4: 递归(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)
开辟辅助数组，新建表头反转，就地反转，递归反转
# -*- coding: utf-8 -*-
'''
链表逆序
'''
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
'''
第一种方法：
对于一个长度为n的单链表head,用一个大小为n的数组arr储存从单链表从头
到尾遍历的所有元素，在从arr尾到头读取元素简历一个新的单链表
时间消耗O(n),空间消耗O(n)
'''
def reverse_linkedlist1(head):
if head == None or head.next == None: #边界条件
return head
arr = [] # 空间消耗为n,n为单链表的长度
while head:
arr.append(head.val)
head = head.next
newhead = ListNode(0)
tmp = newhead
for i in arr[::-1]:
tmp.next = ListNode(i)
tmp = tmp.next
return newhead.next
'''
开始以单链表的第一个元素为循环变量cur,并设置2个辅助变量tmp,保存数据;
newhead,新的翻转链表的表头。
时间消耗O(n),空间消耗O(1)
'''
def reverse_linkedlist2(head):
if head == None or head.next == None: #边界条件
return head
cur = head #循环变量
tmp = None #保存数据的临时变量
newhead = None #新的翻转单链表的表头
while cur:
tmp = cur.next
cur.next = newhead
newhead = cur # 更新 新链表的表头
cur = tmp
return newhead
'''
开始以单链表的第二个元素为循环变量，用2个变量循环向后操作,并设置1个辅助变量tmp,保存数据;
时间消耗O(n),空间消耗O(1)
'''
def reverse_linkedlist3(head):
if head == None or head.next == None: #边界条件
return head
p1 = head #循环变量1
p2 = head.next #循环变量2
tmp = None #保存数据的临时变量
while p2:
tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
head.next = None
return p1
'''
递归操作，先将从第一个点开始翻转转换从下一个节点开始翻转
直至只剩一个节点
时间消耗O(n),空间消耗O(1)
'''
def reverse_linkedlist4(head):
if head is None or head.next is None:
return head
else:
newhead=reverse_linkedlist4(head.next)
head.next.next=head
head.next=None
return newhead
def create_ll(arr):
pre = ListNode(0)
tmp = pre
for i in arr:
tmp.next = ListNode(i)
tmp = tmp.next
return pre.next
def print_ll(head):
tmp = head
while tmp:
print tmp.val
tmp=tmp.next
a = create_ll(range(5))
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist1(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist2(a)
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist3(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist4(a)
print_ll(a) # 0 1 2 3 4
到此这篇关于用python介绍4种常用的单链表翻转的方法小结的文章就介绍到这了,更多相关python 单链表翻转内容请搜索小牛知识库以前的文章或继续浏览下面的相关文章希望大家以后多多支持小牛知识库！
-
本文向大家介绍用Python解析XML的几种常见方法的介绍，包括了用Python解析XML的几种常见方法的介绍的使用技巧和注意事项，需要的朋友参考一下 一、简介 XML（eXtensible Markup Language）指可扩展标记语言，被设计用来传输和存储数据，已经日趋成为当前许多新生技术的核心，在不同的领域都有着不同的应用。它是web发展到一定阶段的必然产物，既具有SGML的
-
本文向大家介绍简单介绍Python中用于求最小值的min()方法，包括了简单介绍Python中用于求最小值的min()方法的使用技巧和注意事项，需要的朋友参考一下 min()方法返回它的参数最小值：最接近负无穷大的值。 语法 以下是min()方法的语法： 参数 x -- 这是一个数值表达式。 y -- 这也是一个数值表达式。 z -- 这也是一个数值表达式。 返回值 此方
-
本文向大家介绍Python实现字符串反转的常用方法分析【4种方法】，包括了Python实现字符串反转的常用方法分析【4种方法】的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了Python实现字符串反转的常用方法。分享给大家供大家参考，具体如下： 下面是实现python字符串反转的四种方法： 1. 切片 这是采用切片的方法，设置步长为-1，也就是反过来排序。 这种方法是最简洁的，也是最推荐的
-
本文向大家介绍js读取json的两种常用方法示例介绍，包括了js读取json的两种常用方法示例介绍的使用技巧和注意事项，需要的朋友参考一下 方法一：js中最著名的eval方法 此方法需要注意的是： 对象表达式{'name':'张三'}必须用“（）”扩住，否则 必须把对象表达式扩起来eval执行才能生成一个匿名对象! 方法二：函数构造定义法返回
-
本文向大家介绍C#中4种深拷贝方法介绍，包括了C#中4种深拷贝方法介绍的使用技巧和注意事项，需要的朋友参考一下 1：利用反射实现 2：利用xml序列化和反序列化实现 3：利用二进制序列化和反序列化实现 4：利用silverlight DataContractSerializer实现，用于在silverlight 客户端使用 补充：第一个已经通过递归实现了深拷贝。
-
本文向大家介绍简单介绍Python中的round()方法，包括了简单介绍Python中的round()方法的使用技巧和注意事项，需要的朋友参考一下 round()方法返回 x 的小数点四舍五入到n个数字。 语法 以下是round()方法的语法： 参数 x --这是一个数值表达式 n --这也是一个数值表达式 返回值 该方法返回 x 的小数点四舍五入到n个数字 例子 下面的例子显示