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 

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

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

相关文章

Django用户认证系统 User对象解析

User对象 User对象是认证系统的核心。用户对象通常用来代表网站的用户,并支持例如访问控制、注册用户、关联创建者和内容等。在Django认证框架中只有一个用户类,例如超级用户('s...

python获取微信企业号打卡数据并生成windows计划任务

python获取微信企业号打卡数据并生成windows计划任务

由于公司的系统用的是Java版本,开通了企业号打卡之后又没有预算让供应商做数据对接,所以只能自己捣鼓这个,以下是个人设置的一些内容,仅供大家参考 安装python python的安装,这...

python与sqlite3实现解密chrome cookie实例代码

本文研究的主要问题:有一个解密chrome cookie的事情,google出了代码,却不能正常执行,原因在于sqlite3的版本太低,虽然我切换到了python3.5的环境,但sqli...

python列表每个元素同增同减和列表元素去空格的实例

python列表每个元素同增同减和列表元素去空格的实例

如下所示: import os var = [1, 2, 3] data = [x*2 for x in var] print (data) two = [[i, i**2] f...

Python基于matplotlib画箱体图检验异常值操作示例【附xls数据文件下载】

Python基于matplotlib画箱体图检验异常值操作示例【附xls数据文件下载】

本文实例讲述了Python基于matplotlib画箱体图检验异常值操作。分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 imp...