Python数据结构之翻转链表
作者:lqh 时间:2023-05-27 20:09:11
翻转一个链表
样例:给出一个链表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,数据结构,链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python使用Pillow添加水印
2021-01-28 08:30:50
![](https://img.aspxhome.com/file/2023/1/78631_0s.jpg)
python selenium在打开的浏览器中动态调整User Agent
2022-09-26 13:41:59
![](https://img.aspxhome.com/file/2023/8/133308_0s.png)
Tab(选项卡)的产品设计原则及应用[译]
2009-07-09 19:05:00
![](https://img.aspxhome.com/file/UploadPic/20097/9/01-24s.gif)
Pandas替换及部分替换(replace)实现流程详解
2023-11-04 02:58:38
![](https://img.aspxhome.com/file/2023/9/125179_0s.png)
Python中常用的8种字符串操作方法
2023-05-28 09:44:38
![](https://img.aspxhome.com/file/2023/6/87886_0s.jpg)
详解Python如何实现尾递归优化
2023-11-13 04:20:06
![](https://img.aspxhome.com/file/2023/1/63621_0s.jpg)
sql怎样显示出评论最多的文章?
2008-08-08 12:17:00
HTML4标签的默认样式列表
2007-09-28 22:00:00
详解RIFF和WAVE音频文件格式
2023-03-30 15:58:13
![](https://img.aspxhome.com/file/2023/1/132391_0s.png)
Python+SeaTable实现生成条形码图片并写入表格
2022-09-04 22:13:26
![](https://img.aspxhome.com/file/2023/5/124395_0s.png)
Python实现的栈(Stack)
2022-12-18 20:35:51
python+opencv边缘提取与各函数参数解析
2023-12-24 11:17:54
![](https://img.aspxhome.com/file/2023/7/124667_0s.png)
分享自己用JS做的扫雷小游戏
2024-04-30 08:54:19
![](https://img.aspxhome.com/file/2023/4/132644_0s.jpg)
Google的设计导引
2008-04-06 14:18:00
纯JavaScript 实现flappy bird小游戏实例代码
2024-05-11 09:05:57
![](https://img.aspxhome.com/file/2023/8/127188_0s.png)
使用 prometheus python 库编写自定义指标的方法(完整代码)
2021-03-03 06:03:58
ueditor编辑器不能上传图片问题的解决方法
2023-09-16 04:55:03
Python常用模块之requests模块用法分析
2023-12-30 15:11:49
Python对列表排序的方法实例分析
2023-03-02 18:26:57
GO语言延迟函数defer用法详解
2024-02-18 16:56:27
![](https://img.aspxhome.com/file/2023/8/105128_0s.png)