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网络应用开发知识点浅析

发送电子邮件 在即时通信软件如此发达的今天,电子邮件仍然是互联网上使用最为广泛的应用之一,公司向应聘者发出录用通知、网站向用户发送一个激活账号的链接、银行向客户推广它们的理财产品等几乎...

pycharm debug功能实现跳到循环末尾的方法

pycharm debug功能实现跳到循环末尾的方法

可以使用条件断点,如图,在断点上右键可以设置,条件自己输入,python语法: 以上这篇pycharm debug功能实现跳到循环末尾的方法就是小编分享给大家的全部内容了,希望能给大家...

Python实现二叉搜索树

Python实现二叉搜索树

二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的。我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈...

探究Python中isalnum()方法的使用

 isalnum()方法检查判断字符串是否包含字母数字字符。 语法 以下是isalnum()方法的语法: str.isa1num() 参数  &nbs...

selenium跳过webdriver检测并模拟登录淘宝

selenium跳过webdriver检测并模拟登录淘宝

简介 模拟登录淘宝已经不是一件新鲜的事情了,过去我曾经使用get/post方式进行爬虫,同时也加入IP代理池进行跳过检验,但随着大型网站的升级,采取该策略比较难实现了。因为你使用get/...