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中的time和datetime的常用方法

一、time的常用方法: import time,datetime # 时间有三种展现方式:时间戳,时间元组,格式化的时间 print(time.time())#当前时间戳 pri...

python画图的函数用法以及技巧

python画图的函数用法以及技巧

对于刚刚学习编程的同学来说对编程是非常陌生的,对很多的代码也是非常陌生,高中忙于学习的我们甚至可以说是对编程是一无所知,进入大学进入到这个专业才开始接触很多电脑相关的东西才开始接触编程,...

Python基于贪心算法解决背包问题示例

本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优...

Python浅拷贝与深拷贝用法实例

本文实例讲述了Python浅拷贝与深拷贝用法。分享给大家供大家参考。具体分析如下: >>> person=['name',['savings',100]] >...

如何使用Python实现自动化水军评论

如何使用Python实现自动化水军评论

前言 玩博客一个多月了,渐渐发现了一些有意思的事,经常会有人用同样的评论到处刷,不知道是为了加没什么用的积分,还是纯粹为了表达楼主好人。那么问题来了,这种无聊的事情当然最好能够自动化咯,...