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简单实现自动删除目录下空文件夹的方法

本文实例讲述了Python简单实现自动删除目录下空文件夹的方法。分享给大家供大家参考,具体如下: 总是发现电脑用上一段时间,各种软件生成各种目录,可是这些目录都是空文件夹,感觉没用,或许...

pytorch 自定义数据集加载方法

pytorch 官网给出的例子中都是使用了已经定义好的特殊数据集接口来加载数据,而且其使用的数据都是官方给出的数据。如果我们有自己收集的数据集,如何用来训练网络呢?此时需要我们自己定义好...

python处理大数字的方法

本文实例讲述了python处理大数字的方法。分享给大家供大家参考。具体实现方法如下: def getFactorial(n): """returns the factorial...

Pycharm学习教程(1) 定制外观

Pycharm学习教程(1) 定制外观

  Pycharm作为一款强力的Python IDE,在使用过程中感觉一直找不到全面完整的参考手册,因此决定对官网的Pycharm教程进行简要翻译,与大家分享。 1、准备工作   首先...

Python 计算任意两向量之间的夹角方法

Python 计算任意两向量之间的夹角方法

如图所示,我们要计算任意两个向量之间的夹角。 (图中的坐标数字是估计值,随手给定) python代码如下 import math AB = [1,-3,5,-1] CD = [...