python链表的反转
反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
题解
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: """ 解题思路: 1.新建一个头指针 2.遍历head链表,依次在新的头节点位置插入,达到反转的效果 """ def reverseList(self, head: ListNode) -> ListNode: # 循环 new_head = None while head: per = head.next # pre 为后置节点,及当前节点的下一个节点 head.next = new_head # 插入头节点元素 new_head = head # 把串起来的链表赋值给头指针 head = per # 向后移一个单位 return new_head # 返回一个新的链表
python反转链表相关技巧
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。
输入:
{1,2,3}
返回值:
{3,2,1}
先来看最基本的反转链表代码:
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here cur = pHead pre = None while cur: nextNode = cur.next cur.next = pre pre = cur cur = nextNode return pre
关键公式
抓住几个关键点:
cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点
pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。
while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件
反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。
对于反转链表的问题,抓住原链表的头节点、原链表的尾节点、反转循环条件、反转链表的尾节点这几个主要角色,基本没什么问题。
接下来,举两个例子:
链表内指定区间反转
链表中的节点每k个一组翻转
链表内指定区间反转
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1)。
要求:时间复杂度 O(n) ,空间复杂度 O(n)
进阶:时间复杂度 O(n),空间复杂度 O(1)
输入:
{1,2,3,4,5},2,4
返回值:
{1,4,3,2,5}
套用公式
这道题目和baseline的区别是,是将对整个链表的反转改成链表 m 位置到 n 位置之间的区间反转,来套一下公式:
原链表的头节点:cur:从head出发,再走m-1步,到达cur
原链表的尾节点:pre:cur前面的节点
反转循环条件:for i in range(n,m)
反转链表的尾节点:需要保存下从head出发,再走m-1步,到达cur时,此时pre的位置 prePos。prePos.next是反转链表的尾节点
和前面的比,需要额外注意下:
需要保存下从head出发,再走m-1步,到达cur时,此时pre的位置 prePos。在反转循环结束后,再进行穿针引线
由于不是对整个链表进行反转,最好新建虚拟头节点dummpyNode,dummpyNode.next指向整个链表
代码实现
先看下套公式部分的代码:
# 找到pre和cur i = 1 while i<m: pre = cur cur = cur.next i = i+1 # 在指定区间内反转 preHead = pre while i<=n: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1
穿针引线部分代码:
nextNode = preHead.next preHead.next = pre if nextNode: nextNode.next = cur
完整代码:
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseBetween(self , head , m , n ): # write code here dummpyNode = ListNode(-1) dummpyNode.next = head pre = dummpyNode cur = head i = 1 while i<m: pre = cur cur = cur.next i = i+1 preHead = pre while i<=n: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1 nextNode = preHead.next preHead.next = pre if nextNode: nextNode.next = cur return dummpyNode.next
链表中的节点每k个一组翻转
将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
要求空间复杂度 O(1),时间复杂度 O(n)
输入:
{1,2,3,4,5},2
返回值:
{2,1,4,3,5}
套用公式
这道题目和baseline的区别是,是将对整个链表的反转改成每k个一组反转,如果节点数不是k的倍数,剩下的节点保持原样。
先分段来看,假设面对位置1-位置k的链表:
原链表的头节点:cur:从head出发,再走k-1步,到达cur
原链表的尾节点:pre:cur前面的节点
反转循环条件:for i in range(1,k)
反转链表的尾节点:先定义tail=head,等反转完后tail.next就是反转链表的尾节点
先看下套公式部分的代码:
pre = None cur = head tail = head i = 1 while i<=k: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1
这样,我们就得到了1 位置1-位置k的反转链表。
此时:
pre:指向反转链表的头节点
cur:位置k+1的节点,下一段链表的头节点
tail:反转链表的尾节点
那么,得到位置k+1-位置2k的反转链表,就可以用递归的思路,用tail.next=reverse(cur,k)
需要注意:如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
i = 1 tmp = cur while i<=k: if tmp: tmp = tmp.next else: return head i = i+1
代码实现
完整代码:
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseKGroup(self , head , k ): # write code here return self.reverse(head, k ) def reverse(self , head , k ): pre = None cur = head tail = head i = 1 tmp = cur while i<=k: if tmp: tmp = tmp.next else: return head i = i+1 i = 1 while i<=k: nextNode = cur.next cur.next = pre pre = cur cur = nextNode i = i+1 tail.next = self.reverse(cur, k) return pre
好了,抓住几个关键点:
cur:原链表的头节点,在反转结束时,cur指向pre的下一个节点
pre:原链表的尾节点,也就是反转后链表的头节点。最终返回的是pre。
while cur:表示反转循环的条件,这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件
反转链表的尾节点,这里的尾节点是None,后面会提到显式指定。
以上是python链表的反转方式是什么的详细内容。更多信息请关注PHP中文网其他相关文章!

Python在web开发、数据科学、机器学习、自动化和脚本编写等领域有广泛应用。1)在web开发中,Django和Flask框架简化了开发过程。2)数据科学和机器学习领域,NumPy、Pandas、Scikit-learn和TensorFlow库提供了强大支持。3)自动化和脚本编写方面,Python适用于自动化测试和系统管理等任务。

两小时内可以学到Python的基础知识。1.学习变量和数据类型,2.掌握控制结构如if语句和循环,3.了解函数的定义和使用。这些将帮助你开始编写简单的Python程序。

如何在10小时内教计算机小白编程基础?如果你只有10个小时来教计算机小白一些编程知识,你会选择教些什么�...

使用FiddlerEverywhere进行中间人读取时如何避免被检测到当你使用FiddlerEverywhere...

Python3.6环境下加载Pickle文件报错:ModuleNotFoundError:Nomodulenamed...

如何解决jieba分词在景区评论分析中的问题?当我们在进行景区评论分析时,往往会使用jieba分词工具来处理文�...

如何使用正则表达式匹配到第一个闭合标签就停止?在处理HTML或其他标记语言时,常常需要使用正则表达式来�...

攻克Investing.com的反爬虫策略许多人尝试爬取Investing.com(https://cn.investing.com/news/latest-news)的新闻数据时,常常�...


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

WebStorm Mac版
好用的JavaScript开发工具

禅工作室 13.0.1
功能强大的PHP集成开发环境

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中