单链表反转python实现代码示例

yipeiwu_com6年前Python基础

单链表的反转可以使用循环,也可以使用递归的方式

1.循环反转单链表

循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。

代码:

class ListNode: 
  def __init__(self,x): 
    self.val=x; 
    self.next=None; 
 
def nonrecurse(head):       #循环的方法反转链表 
  if head is None or head.next is None: 
    return head; 
  pre=None; 
  cur=head; 
  h=head; 
  while cur: 
    h=cur; 
    tmp=cur.next; 
    cur.next=pre; 
    pre=cur; 
    cur=tmp; 
  return h; 
   
head=ListNode(1);  #测试代码 
p1=ListNode(2);   #建立链表1->2->3->4->None; 
p2=ListNode(3); 
p3=ListNode(4); 
head.next=p1; 
p1.next=p2; 
p2.next=p3; 
p=nonrecurse(head);  #输出链表 4->3->2->1->None 
while p: 
  print p.val; 
  p=p.next; 

结果:

4
3
2
1
>>>

2.递归实现单链表反转

class ListNode: 
  def __init__(self,x): 
    self.val=x; 
    self.next=None; 
 
   
def recurse(head,newhead):  #递归,head为原链表的头结点,newhead为反转后链表的头结点 
  if head is None: 
    return ; 
  if head.next is None: 
    newhead=head; 
  else : 
    newhead=recurse(head.next,newhead); 
    head.next.next=head; 
    head.next=None; 
  return newhead; 
   
head=ListNode(1);        #测试代码 
p1=ListNode(2);         # 建立链表1->2->3->4->None 
p2=ListNode(3); 
p3=ListNode(4); 
head.next=p1; 
p1.next=p2; 
p2.next=p3; 
newhead=None; 
p=recurse(head,newhead);      #输出链表4->3->2->1->None 
while p: 
  print p.val; 
  p=p.next; 

运行结果同上。

总结

以上就是本文关于单链表反转python实现代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

相关文章

python3.5 cv2 获取视频特定帧生成jpg图片

python3.5 cv2 获取视频特定帧生成jpg图片

假如文件夹有大量视频文件,需求目标是想从每个视频中提取一帧作为视频的一个封面图片,本文利用opencv-python模块实现需求。结合自己的工作,做一下简单的记录,原本想生成可传参数的e...

python 使用plt画图,去除图片四周的白边方法

python 使用plt画图,去除图片四周的白边方法

用matplotlib.pyplot画的图,显示和保存的图片周围都会有白边,可以去掉。为了显示的更清楚,给图片加了红色的框 代码 “` import matplotlib.pypl...

Python中列表的一些基本操作知识汇总

Python中列表的一些基本操作知识汇总

 Python最基本的数据结构是序列(列表/元组)。一个序列中的每个元素都分配有一个数字- 它的位置或索引。第一个索引是0,第二个索引是1,依此类推。 Python有6内置类型...

Flask框架使用DBUtils模块连接数据库操作示例

本文实例讲述了Flask框架使用DBUtils模块连接数据库的操作方法。分享给大家供大家参考,具体如下: Flask连接数据库 数据库连接池: Django使用:django ORM(p...

Python urlopen()函数 示例分享

好了,废话少说,我们先看看几个示例吧 一、打开一个网页获取所有的内容 复制代码 代码如下:from urllib import urlopendoc = urlopen("http://...