python反转单链表算法题
作者:小小小小人ksh 发布时间:2023-04-02 04:26:49
现在算法是大厂面试的必考题,而且越来越难,已经不是简单的列表,字符串操作了,会涉及到各种数据结结构。单链表的反转也是经常考的一道题,里面故在此记录一下。
1.链表的特点:
顺序存储元素,但是元素在空间上是不连续的,所以在链表每个元素中除了存储元素的值,还会存储下一个元素的地址,单链表的话就只有指向下一个元素的指针,双向链表的话还会有指向前一个元素的指针。正是由于链表以上的存储特点,在做插入和删除操作时只需要断开指针的连接,不需要移动后面的数据,所以对链表修改的效率会很高,但是查找的效率会很低,这也正是链表和数组的区别。链表的存储示意图:
完成这道题至少有3种方式:
1.先对原链表做头部删操作,再对新链表做头部插入操作;
2.通过3个指针实现,p0指向前一个节点的指针,p1表示当前节点的指针,p2表示下一个节点的指针
3.用递归实现;
2.方式一:
1)创建一个新的空列表;
2)取出旧链表中头结点的元素,将其next指针设置为新链表的头指针,同时将旧链表的头结点执行下一个元素
3)依次重复第2)步的操作,直到取出就链表中所有的节点。
4)最后形成的新链表如下,实现了反转的功能:
5)代码实现:
# encoding=utf-8
import copy
class Node:
"""节点类,包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self):
"""反转单向列表
思路一:先对原链表做头删操作,再对新链表做头插
"""
# 定义一个新的链表
new_list_node = LinkedList()
temp = copy.deepcopy(self.head)
while temp:
# 1.对之前的链表做头删除操作
node = temp
temp = temp.next
# 2.对新的链表做头插入操作
if new_list_node.head is None:
new_list_node.tail = node
node.next = new_list_node.head
new_list_node.head = node
return new_list_node
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list()
print(new_list_node.get_all())
print(new_list_node.tail)
3.方式二
借助3个指针来实现反转,p0之前前一个节点,p1指向当前操作的节点,p2指向下一个节点。操作过程如下:将p1的next指针之前p0,之后将p0指向p1节点,p1指向p2节点,如果p1不为空,重复以上操作,最后,p0即为新列表的头节点。
1)开始时p0为空;将p1指向链表的头节点,p1节点的next指针指向p0;p2指向下一个节点:
2)调整3个指针的指向:将p0指向p1;p1指向p2,p1的next指向p0;p2指向下一个节点
3)循环执行以上步骤,直到p1指向的节点不为空,最后得到的链表为:
4)代码实现:
# encoding=utf-8
import copy
class Node:
"""节点类,包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self):
"""
反转单向列表
思路二:通过3个指针实现,p0指向前一个节点的指针,p1表示当前节点的指针,p2表示下一个节点的指针
:return: LinkedList 对象
"""
p1 = copy.deepcopy(self.head)
p2 = p1.next
# 定义一个新的链表对象
new_list_node = LinkedList()
while p1:
if new_list_node.head is None:
new_list_node.tail = p1
# 将p1的next指向新链表的头结点
p1.next = new_list_node.head
# 将新链表的头结点指向p1
new_list_node.head = p1
# 将p1指向p2
p1 = p2
# 判断p2是否指向了链表的末尾
if p2:
p2 = p2.next
return new_list_node
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list()
print(new_list_node.get_all())
print(new_list_node.tail)
4.方式三:
递归就是将问题分解为处理过程一致的子问题进行处理,但是一定要要结束条件。链表的反转也可以采用递归的方式实现,每次传入的节点不是最后一个的话,就将下一个节点作为参数传递进去,递归调用;直到传入的是最后一个节点时开始逐级返回。
1)将链表中每个节点作为参数,依次传入到reverse_list函数中;
2)当传入的是最后一个节点时,以此节点为头结点创建一个新的链表,并将此链表返回;
3)上一级的调用者接受到返回的链表后,将传入的节点作为链表的尾结点放到链表中;
4)逐级返回,直到回到最开始执行reverse_list函数中,将生成的新链表返回即可
5)代码实现:
# encoding=utf-8
import copy
class Node:
"""节点类,包含值和下一个节点的指针"""
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
return "Node value:%s" % self.value
class LinkedList:
def __init__(self, head=None, tail=None):
self.head = head
self.tail = tail
def get_all(self):
"""获取链表中所有的节点"""
nodes = []
temp = self.head
while temp:
nodes.append(temp.value)
temp = temp.next
return nodes
def add_node(self, value):
"""在列表中添加节点"""
node = Node(value)
# 空链表,收尾指针都指向新增加的节点
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def reverse_list(self, node):
"""
反转单链表
思路三:用递归实现
:return:LinkedList 对象
"""
if node.next is None:
return LinkedList(node, node)
temp = copy.deepcopy(node)
# 断开当前节点的连接
temp.next = None
# 将当前节点放到内层递归返回的链表结尾
l = self.reverse_list(node.next)
l.tail.next = temp
l.tail = temp
return l
if __name__ == "__main__":
l = LinkedList()
for i in range(5):
l.add_node(i)
new_list_node = l.reverse_list1()
print(new_list_node.get_all())
print(new_list_node.tail)
来源:https://blog.csdn.net/kongsuhongbaby/article/details/106630731
猜你喜欢
- 一、实现过程终端的字符颜色是用转义序列控制的,是文本模式下的系统显示功能,和具体的语言无关转义序列是以ESC开头,即用\033来完成(ESC
- 通过使用zabbix 日志监控 我发现一个问题 例如oracle的日志有报错的情况 ,通常不会去手动清理 这样的话当第二次有日志写进来的时候
- ---- Oracle是关系型数据库管理系统,它功能强大、性能卓越,在当今大型数据库管理系统中占有重要地位。在我们开发的一MIS
- 注意:我使用的是 Entity Framework Core 2.0 (2.0.0-preview2-final)。正式版发布时,功能可能存
- 一、分类问题损失函数——交叉熵(crossentropy)交叉熵刻画了两个概率分布之间的距离,是分类问题中使用广泛的损失函数。给定两个概率分
- 我们使用的是QWebview模块,这里也主要是展示下QWebview的用法。之前在网上找了半天的解析网页的内容,都不是很清楚。这是核心代码:
- 列表 List列表是任意对象的集合,在 Python 中通过逗号分隔的对象序列括在方括号 ( [] ) 中people_list = [
- 看了不少朋友的个人网站,有一个小问题,似乎很多朋友都忽略了,那就是版权声明的写法。虽然那只是一小行字,不过作为设计师也好,作为个人的爱好也好
- 在本教程中,我们将构建一个程序,该程序可以使用流行的计算机视觉库 OpenCV 确定对象的方向(即以度为单位的旋转角度)。最常见的现实世界用
- 一、基本思想本文思想是基于用asp和DOM来读取和存储XML数据,并利用XML数据来存储留言信息,达到同用数据库存储数据的功能。二、XML留
- 本文实例讲述了利用PHP函数计算中英文字符串长度的方法。分享给大家供大家参考。具体实现方法如下:一般来说大家知道英文字符占一个字节,而中文字
- 1.本人第一次学python做出来的,当时满满的成就感,当作纪念!!!!!非常简单,复制即可使用代码块import json#把字符串类型的
- <%''调用例子'Dim int_RPP,int_Start,int_showNumberLink
- 通过引用serial模块包,来操作串口。1、查看串口名称在Linux和Windows中,串口的名字规则不太一样。需要事先查看。Linux下的
- 1.使用iloc对数据进行批量修改使用iloc最简单的就是将数据批量修改为某个特定的值以下是我随便写入的数据:现在将[‘
- 1.JOIN和UNION区别 join 是两张表做交连后里面条件相同的部分记录产生一个记录集, union是产生的两个记录集(字段要一样的)
- python 3.x 环境下,使用h5py加载HDF5文件,查看keys,如下:>>> import h5py>&g
- 一、决策树的特点1.优点具有很好的解释性,模型可以生成可以理解的规则。可以发现特征的重要程度。模型的计算复杂度较低。2.缺点模型容易过拟合,
- Python爬虫、数据分析、网站开发等案例教程视频免费在线观看https://space.bilibili.com/523606542Sel
- apply_async简介python在同一个线程中多次执行同一方法时,该方法执行耗时较长且每次执行过程及结果互不影响,如果只在主进程中执行