用python介绍4种常用的单链表翻转的方法小结
如何把一个单链表进行反转？
方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。
方法2：使用3个指针遍历单链表，逐个链接点进行反转。
方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。
方法4:递归(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)
开辟辅助数组，新建表头反转，就地反转，递归反转
#-*-coding:utf-8-*- ''' 链表逆序 ''' classListNode: def__init__(self,x): self.val=x self.next=None ''' 第一种方法： 对于一个长度为n的单链表head,用一个大小为n的数组arr储存从单链表从头 到尾遍历的所有元素，在从arr尾到头读取元素简历一个新的单链表 时间消耗O(n),空间消耗O(n) ''' defreverse_linkedlist1(head): ifhead==Noneorhead.next==None:#边界条件 returnhead arr=[]#空间消耗为n,n为单链表的长度 whilehead: arr.append(head.val) head=head.next newhead=ListNode(0) tmp=newhead foriinarr[::-1]: tmp.next=ListNode(i) tmp=tmp.next returnnewhead.next ''' 开始以单链表的第一个元素为循环变量cur,并设置2个辅助变量tmp,保存数据; newhead,新的翻转链表的表头。 时间消耗O(n),空间消耗O(1) ''' defreverse_linkedlist2(head): ifhead==Noneorhead.next==None:#边界条件 returnhead cur=head#循环变量 tmp=None#保存数据的临时变量 newhead=None#新的翻转单链表的表头 whilecur: tmp=cur.next cur.next=newhead newhead=cur#更新新链表的表头 cur=tmp returnnewhead ''' 开始以单链表的第二个元素为循环变量，用2个变量循环向后操作,并设置1个辅助变量tmp,保存数据; 时间消耗O(n),空间消耗O(1) ''' defreverse_linkedlist3(head): ifhead==Noneorhead.next==None:#边界条件 returnhead p1=head#循环变量1 p2=head.next#循环变量2 tmp=None#保存数据的临时变量 whilep2: tmp=p2.next p2.next=p1 p1=p2 p2=tmp head.next=None returnp1 ''' 递归操作，先将从第一个点开始翻转转换从下一个节点开始翻转 直至只剩一个节点 时间消耗O(n),空间消耗O(1) ''' defreverse_linkedlist4(head): ifheadisNoneorhead.nextisNone: returnhead else: newhead=reverse_linkedlist4(head.next) head.next.next=head head.next=None returnnewhead defcreate_ll(arr): pre=ListNode(0) tmp=pre foriinarr: tmp.next=ListNode(i) tmp=tmp.next returnpre.next defprint_ll(head): tmp=head whiletmp: printtmp.val tmp=tmp.next a=create_ll(range(5)) print_ll(a)#01234 a=reverse_linkedlist1(a) print_ll(a)#43210 a=reverse_linkedlist2(a) print_ll(a)#01234 a=reverse_linkedlist3(a) print_ll(a)#43210 a=reverse_linkedlist4(a) print_ll(a)#01234
到此这篇关于用python介绍4种常用的单链表翻转的方法小结的文章就介绍到这了,更多相关python单链表翻转内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。