用python介绍4种常用的单链表翻转的方法小结-创新互联
如何把一个单链表进行反转?
创新互联公司于2013年成立,先为罗山等服务建站,罗山等地企业,进行企业商务咨询服务。为罗山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转。
方法2:使用3个指针遍历单链表,逐个链接点进行反转。
方法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种常用的单链表翻转的方法小结-创新互联
URL网址:http://pwwzsj.com/article/cdgoes.html