Python数据结构之翻转链表

yipeiwu_com5年前Python基础

翻转一个链表

样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

一种比较简单的方法是用“摘除法”。就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点。

那样例来说,步骤是这样的:

1. 新建空节点:None
2. 1->None
3. 2->1->None
4. 3->2->1->None

代码就非常简单了:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here 

当然,还有一种稍微难度大一点的解法。我们可以对链表中节点依次摘链和链接的方法写出原地翻转的代码:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here 

需要注意的是,做摘链的时候,不要忘了把摘除的地方再连起来

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

相关文章

python中将zip压缩包转为gz.tar的方法

由于同事电脑上没有直接可以压缩gz.tar格式的压缩软件,而工作中这个又时常需要将zip文件转换为gz.tar格式,所以常常将压缩为zip格式的文件发给我来重新压缩成gz.tar格式发给...

Python列表删除元素del、pop()和remove()的区别小结

前言 在python列表的元素删除操作中, del, pop(), remove()很容易混淆, 下面对三个语句/方法作出解释 del语句 del语句可以删除任何位置处的列表元素, 若...

django query模块

最近在接触一个Django项目,使用的是fbv( function-base views )模式,看起来特别不舒服,项目中有一个模型类117个字段,看我的有点晕,不过还是得干呀,生活呀,...

探究python中open函数的使用

探究python中open函数的使用

最近,开始学习python的开发,遇到了一点文件操作的问题,探究一下open函数的使用。 一、open()的函数原型 open(file, mode=‘r', buffering=-1,...

Python bsddb模块操作Berkeley DB数据库介绍

bsddb模块是用来操作bdb的模块,bdb是著名的Berkeley DB,它的性能非常好,mysql的存储后端引擎都支持bdb的方式。这里简单介绍一些关于bsddb的使用方法。 bdb...