Python数据结构之翻转链表

yipeiwu_com6年前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实现根据文件格式分类

python实现根据文件格式分类

本文实例为大家分享了python根据文件格式分类的具体代码,供大家参考,具体内容如下 使用到python内置os模块(对目录或文件的新建/删除/属性查看,还提供了对文件以及目录的路径操作...

CentOS 7下安装Python 3.5并与Python2.7兼容并存详解

CentOS 7下安装Python 3.5并与Python2.7兼容并存详解

本文主要给大家介绍了关于在CentOS 7下安装Python 3.5并与Python2.7兼容并存的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍: CentOS 7下安装P...

Python文本相似性计算之编辑距离详解

Python文本相似性计算之编辑距离详解

编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符,插入一...

浅谈python函数之作用域(python3.5)

1 基本概念 1.1 命名空间 (namespace) 命名空间是变量名到对象的映射(name -> obj)。目前大多数的命名空间以类似于python字典的形式实现,实现形式在未...

简单解决Python文件中文编码问题

简单解决Python文件中文编码问题

读写中文 需要读取utf-8编码的中文文件,先利用sublime text软件将它改成无DOM的编码,然后用以下代码: with codecs.open(note_path, 'r+...