这篇文章主要介绍了用python介绍4种常用的单链表翻转的方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

如何把一个单链表进行反转?

方法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种常用的单链表翻转的方法小结的文章就介绍到这了,更多相关python 单链表翻转内容请搜索爱安网以前的文章或继续浏览下面的相关文章希望大家以后多多支持爱安网! 

最新资讯
微软承认Win10存在严重NTFS漏洞:解压缩包等会损坏硬盘

微软承认Win10存在严

现在微软证实了这个消息,并且表示,会在后续的更新中修复
滴滴在北京已完成46787名司机接种疫苗 预约接种超10万人

滴滴在北京已完成4678

截止1月16日14点,在防疫部门的指导部署下,已完成46787名
高德打车北京升级疫情防控:要求合作平台完成驾驶员全员接种疫苗

高德打车北京升级疫情

为严格执行北京新冠肺炎疫情防控要求,保障广大驾驶员和
Uber计划分拆Postmates旗下快递机器人部门

Uber计划分拆Postmate

据Tech Crunch报道,Uber计划分拆旗下的快递机器人部门P
华为将开设海外最大旗舰店:选址沙特

华为将开设海外最大旗

中国科技公司华为计划在利雅得开设一家旗舰店,这是华为
巴菲特获权证可折价买入2307.69万股传媒公司股票

巴菲特获权证可折价买

伯克希尔·哈撒韦向SEC提交的信息披露报告,巴菲特获权
最新文章
在pycharm中为项目导入anacodna环境的操作方法

在pycharm中为项目导

这篇文章主要介绍了在pycharm中为项目导入anacodna环
tensorflow的ckpt及pb模型持久化方式及转化详解

tensorflow的ckpt及pb

今天小编就为大家分享一篇tensorflow的ckpt及pb模型持
PyTorch笔记之scatter()函数的使用

PyTorch笔记之scatter

这篇文章主要介绍了PyTorch笔记之scatter()函数的使用
python3实现网页版raspberry pi(树莓派)小车控制

python3实现网页版ras

这篇文章主要为大家详细介绍了python3实现网页版raspb
完美解决pycharm导入自己写的py文件爆红问题

完美解决pycharm导入

今天小编就为大家分享一篇完美解决pycharm导入自己写
pycharm内无法import已安装的模块问题解决

pycharm内无法import

今天小编就为大家分享一篇pycharm内无法import已安装