Python算法——链表（反转链表，合并两个排序链表，判断是否有环，链表中倒数最后k个结点，第一个公共结点，删除重复元素）

哈喽大家好，好久不见！又进入新的一个学期，这学期小编要进行python的算法学习啦，今天更新链表的部分题目~

牛客 NC78 反转链表

题目如下：

请添加图片描述
算法思想如下：

1.初始化两个指针pre和cur，分别表示前驱节点和当前节点。初始时，pre为空，cur指向头节点。
2.使用一个循环遍历链表，直到cur为空。
3.在每次循环中，首先保存当前节点的下一个节点到临时变量temp。
4.然后将当前节点的next指针指向前驱节点pre。
5.更新前驱节点pre为当前节点cur。
6.更新当前节点cur为下一个节点temp。
7.当循环结束时，所有节点的next指针都已反转，此时pre指向新的头节点，即反转后的链表的头节点。
8.返回反转后的链表头节点pre。

代码如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
    def ReverseList(self, head: ListNode) -> ListNode:
        pre = None  # 初始化前驱节点为空
        if not head:  # 如果链表为空，直接返回None
            return None
        cur = head  # 当前节点指向头节点
        while cur:  # 遍历链表
            temp = cur.next  # 保存当前节点的下一个节点
            cur.next = pre  # 将当前节点的下一个节点指向前驱节点
            pre = cur  # 更新前驱节点为当前节点
            cur = temp  # 更新当前节点为下一个节点
        return pre  # 返回反转后的链表头节点

牛客 NC33 合并两个有序链表

题目如下：
请添加图片描述
请添加图片描述
算法思想如下：

1. 创建一个新的头结点new，用于存储合并后的链表。
2. 初始化一个指针cur指向新链表的头结点。
3. 判断两个链表是否为空，如果其中一个为空，则直接返回另一个链表。
4. 使用两个指针p1和p2分别遍历两个链表。
5. 比较p1和p2所指向的节点的值，将较小的节点添加到新链表中，并将对应的指针向后移动一位。
6. 重复步骤5，直到其中一个链表遍历完毕。
7. 如果p1还有剩余节点，将其添加到新链表的末尾；如果p2还有剩余节点，将其添加到新链表的末尾。
8. 返回新链表的头结点的下一个节点，即合并后链表的第一个节点。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        new=ListNode(0)
        cur=new
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        p1=pHead1
        p2=pHead2
        while p1 and p2:
            if p1.val<=p2.val:
                cur.next=p1
                p1=p1.next
            else:
                cur.next=p2
                p2=p2.next
            cur=cur.next
        if p1:
            cur.next=p1
        if p2:
            cur.next=p2
        return new.next

牛客 NC4 判断链表是否有环

题目如下：
请添加图片描述
算法思想如下：

1. 初始化两个指针，一个慢指针（low）和一个快指针（fast），都指向链表的头节点。
2. 在循环中，慢指针每次移动一步，快指针每次移动两步。
3. 如果链表中存在环，那么快指针最终会追上慢指针，即它们会在环中的某个位置相遇。
4. 如果链表中不存在环，那么快指针会先到达链表的尾部，此时循环结束，返回False。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        if not head or not head.next:
            return False
        low=head
        fast=head.next
        while fast and fast.next:
            if low!=fast:    
                low=low.next
                fast=fast.next.next
            else:
                return True
        return False

牛客 NC69 链表中倒数最后k个结点

题目如下：
请添加图片描述
算法思想如下：

1.指向链表的头节点pHead。
2. 初始化计数器count为0。
3. 遍历链表，每遍历一个节点，计数器count加1。
4. 如果k大于链表长度count，说明k超出了链表的范围，返回None。
5. 将指针cur重新指向链表头节点pHead。
6. 再次遍历链表，这次遍历到第count-k个节点，即倒数第k个节点。
7. 返回当前指针cur所指向的节点。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param pHead ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        if not pHead or k<=0:
            return None
        cur=pHead
        count=0
        while cur :
            cur=cur.next
            count+=1
        if k>count:
            return None
        cur=pHead
        for _ in range(count-k):
            cur=cur.next
        return cur

牛客 NC66 两个链表的第一个公共结点

题目如下：请添加图片描述
算法思想如下：

1. 首先检查输入的两个链表是否为空，如果有一个为空，则返回None，因为没有公共节点。
2. 初始化两个指针p1和p2分别指向两个链表的头节点。
3. 遍历两个链表，分别计算它们的长度length1和length2。
4. 根据两个链表的长度差值x，将较长链表的指针向前移动x个节点，使得两个链表剩余的长度相等。
5. 同步遍历两个链表，比较当前节点是否相同。如果相同，则找到了第一个公共节点，返回该节点；否则继续遍历。
6. 如果遍历完两个链表都没有找到相同的节点，则返回None。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        if pHead1==None or pHead2==None:
            return None
        p1=pHead1
        p2=pHead2
        length1=0
        length2=0
        while p1:
            p1=p1.next
            length1+=1
        while p2:
            p2=p2.next
            length2+=1
        p1=pHead1
        p2=pHead2
        if length1>=length2:
            x=length1-length2
            for _ in range(x):
                p1=p1.next
        elif length2>length1:
            x=length2-length1
            for _ in range(x):
                p2=p2.next
        while p1 and p2:
            if p1==p2:
                return p1
            else:
                p1=p1.next
                p2=p2.next
        return None

牛客 NC96 判断一个链表是否为回文结构

题目如下：
请添加图片描述
算法思想：

1. 遍历链表，将链表中的元素依次存入一个列表中。
2. 再次遍历这个列表，同时从头部和尾部开始比较元素，如果发现不相等的元素，则说明链表不是回文结构，返回False。
3. 如果所有元素都相等，说明链表是回文结构，返回True。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head: ListNode) -> bool:
        # write code here
        cur=head
        count=0
        mylist=[]
        while cur:
            mylist.append(cur.val)
            cur=cur.next
            count+=1
        for i in range(count):
            if mylist[i]!=mylist[count-i-1]:
                return False
        return True

牛客 NC25 删除有序链表中重复的元素-I

题目如下：
请添加图片描述
算法思想：

1. 首先检查链表是否为空，如果为空则直接返回None。
2. 如果链表只有一个节点，那么没有重复元素，直接返回头节点。
3. 初始化两个指针cur和x，分别指向链表的头节点和第二个节点。
4. 使用while循环遍历链表，直到cur或x为空。
5. 在循环中，比较cur和x的值，如果相等，说明有重复元素，将cur的next指针指向x的下一个节点，即跳过x节点。
6. 如果cur和x的值不相等，将cur和x都向后移动一位。
7. 循环结束后，返回处理后的链表头节点。

代码如下：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        if head is None:
            return None
        if head.next is None:
            return head
        cur=head
        x=head.next
        while cur and x:
            if cur.val==x.val:
                cur.next=x.next
                x=x.next
            else:
                cur=cur.next
                x=x.next
        return head
今天的题目到这里就结束啦~ 如果觉得小编写的不错的话请三连支持一下！ 以后会继续更新优质内容~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/895752.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ERROR [internal] load metadata for docker.io/library/nginx:latest

ERROR [internal] load metadata for docker.io/library/nginx:latest

docker执行错误解决方法 1、执行docker pull nginx2、docker build -t xxx:xx
阅读更多...
Ai环境安装教程

Ai环境安装教程

依赖的驱动软件 python3.115cuda11.4torch2.0.1 一。如何下载安装 一、驱动下载 【Python链接】https://www.python.org/ftp/python/3.11.5/python-3.11.5-amd64.exe 【CUDA链接】https://developer.download.nvidia.com/compute/cuda/11.4.4/local_installers/cuda_11.4.4…
阅读更多...
从 Microsoft 官网下载 Windows 10

从 Microsoft 官网下载 Windows 10

方法一&#xff1a; 打开 Microsoft 官网&#xff1a; 打开开发人员工具&#xff08;按 F12 或右键点击“检查”&#xff09;。 点击“电脑模拟手机”按钮&#xff0c;即下图&#xff1a; 点击后重新加载此网页&#xff0c;即可看到下载选项。
阅读更多...
成都睿明智科技有限公司共创抖音电商新篇章

成都睿明智科技有限公司共创抖音电商新篇章

在当今这个数字化浪潮汹涌的时代&#xff0c;抖音电商以其独特的魅力迅速崛起&#xff0c;成为众多商家竞相追逐的新蓝海。在这片充满机遇与挑战的领域中&#xff0c;成都睿明智科技有限公司凭借其专业的服务、创新的策略和敏锐的市场洞察力&#xff0c;成为了众多商家信赖的合…
阅读更多...
Notepad++将搜索内容所在行选中，并进行复制等操作

Notepad++将搜索内容所在行选中，并进行复制等操作

背景 Notepad在非常多的数据行内容中&#xff0c;按照指定内容检索&#xff0c;并定位到具体行&#xff0c;而后对内容行的数据进行复制、剪切、删除等处理动作。 操作说明 检索并标记所在行 弹出搜索框&#xff1a;按下 Ctrl F。 输入查找字符串&#xff1a;在搜索框中输入要…
阅读更多...
房屋租赁管理系统|基于java和小程序的房屋租赁管理系统小程序设计与实现(源码+数据库+文档)

房屋租赁管理系统|基于java和小程序的房屋租赁管理系统小程序设计与实现(源码+数据库+文档)

房屋租赁管理系统小程序 目录 基于java和小程序的房屋租赁管理系统小程序设计与实现 一、前言 二、系统功能设计 三、系统实现 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大厂码农|毕设…
阅读更多...
java项目之精准扶贫管理系统源码(springboot+mysql+vue)

java项目之精准扶贫管理系统源码(springboot+mysql+vue)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的精准扶贫管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 精准扶贫管理系统的主要…
阅读更多...
STM32重拾+找工作MD

STM32重拾+找工作MD

1.工程文件创建 外部的文件夹要和工程文件对应&#xff0c;也就是外面创建好之后&#xff0c;里面也要对应添加&#xff1b; 首先是startup启动文件&#xff0c;这个是程序执行最基本的文件&#xff0c;keil中启动文件是用汇编写的&#xff0c;启动文件内定义了中断向量表&…
阅读更多...
Java面试指南：Java基础介绍

Java面试指南：Java基础介绍

这是《Java面试指南》系列的第1篇&#xff0c;本篇主要是介绍Java的一些基础内容&#xff1a; 1、Java语言的起源 2、Java EE、Java SE、Java ME介绍 3、Java语言的特点 4、Java和C的区别和联系&#xff1f; 5、面向对象和面向过程的比较 6、Java面向对象的三大特性&#xff1a…
阅读更多...
GitLab 老旧版本如何升级？

GitLab 老旧版本如何升级？

极狐GitLab 正式对外推出 GitLab 专业升级服务 https://dl.gitlab.cn/cm33bsfv&#xff01; 专业的技术人员为您的 GitLab 老旧版本实例进行专业升级&#xff01;服务详情可以在官网查看详细解读&#xff01; 那些因为老旧版本而被攻击的例子 话不多说&#xff0c;直接上图&a…
阅读更多...
QT实现校园导航

QT实现校园导航

导航是地图类项目实战中经常会遇到了。看上去貌似没头绪&#xff0c;其实是有模板遵循的。我们直接根据图看代码。 //MainWidget.h#ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include "mapwidget.h" #include <QToolButton> #in…
阅读更多...
比较相同机器上 redis和mysql分别单独承载的 最大连接数量

比较相同机器上 redis和mysql分别单独承载的 最大连接数量

在相同的机器上&#xff0c;Redis 和 MySQL 的最大连接数量会受到硬件配置&#xff08;如 CPU、内存、网络等&#xff09;、配置参数和应用场景的影响。以下是对 Redis 和 MySQL 在单机环境下最大连接数的比较&#xff1a; Redis 最大连接数量 默认配置&#xff1a; Redis 默…
阅读更多...
【动手学深度学习】7.3 网络中的网络(NiN)（个人向笔记）

【动手学深度学习】7.3 网络中的网络(NiN)（个人向笔记）

LeNet&#xff0c;AlexNet和VGG都有一个共同的设计模型&#xff1a;通过一系列卷积层和汇聚层来提取空间结构特征&#xff0c;然后通过全连接层对特征的表征进行处理AlexNet和VGG对LeNet的改进主要是在于如何扩大和加深这两个模块网络中的网络(NIN)提出了&#xff1a;在每个像素…
阅读更多...
视频云存储/音视频流媒体视频平台EasyCVR视频汇聚平台在欧拉系统中启动失败是什么原因？

视频云存储/音视频流媒体视频平台EasyCVR视频汇聚平台在欧拉系统中启动失败是什么原因？

视频监控/视频集中存储/磁盘阵列EasyCVR视频汇聚平台具备强大的拓展性和灵活性&#xff0c;支持多种视频流的外部分发&#xff0c;如RTMP、RTSP、HTTP-FLV、WebSocket-FLV、HLS、WebRTC、fmp4等&#xff0c;这为其在各种复杂环境下的部署提供了便利。 安防监控EasyCVR视频汇聚平…
阅读更多...
【含开题报告+文档+PPT+源码】贫困儿童一对一扶贫帮扶系统设计与实现

【含开题报告+文档+PPT+源码】贫困儿童一对一扶贫帮扶系统设计与实现

开题报告 根据《中华人民共和国慈善法》第五十八条规定&#xff0c;慈善组织确定慈善受益人&#xff0c;应当坚持公开、公平、公正的原则&#xff0c;不得指定慈善组织管理人员的利害关系人作为受益人[2]。以上所列举的平台基本没有做到公开、公平、公正的原则&#xff0c;例如…
阅读更多...
OpenAI Canvas用户反馈：并不如外界传言般“炸裂”，更不是“AGI的终极交互形态” | LeetTalk Daily...

OpenAI Canvas用户反馈：并不如外界传言般“炸裂”，更不是“AGI的终极交互形态” | LeetTalk Daily...

“LeetTalk Daily”&#xff0c;每日科技前沿&#xff0c;由LeetTools AI精心筛选&#xff0c;为您带来最新鲜、最具洞察力的科技新闻。 Canvas作为一个独立的界面&#xff0c;通过与ChatGPT的结合来提升用户的协作能力和创作效率。尽管用户对其独立性与现有工具的整合存在不同…
阅读更多...
大模型常见算子定义

大模型常见算子定义

本文将汇总大模型常用的算子定义&#xff0c;方便快速根据定义公式评估其计算量。 LayerNorm 这是在BERT、GPT等模型中广泛使用的LayerNorm&#xff1a; RMSNorm RMSNorm(root mean square)发现LayerNorm的中心偏移没什么用(减去均值等操作)。将其去掉之后&#xff0c;效果几乎…
阅读更多...
如何将LiDAR坐标系下的3D点投影到相机2D图像上

如何将LiDAR坐标系下的3D点投影到相机2D图像上

将激光雷达点云投影到相机图像上做数据层的前融合&#xff0c;或者把激光雷达坐标系下标注的物体点云的3d bbox投影到相机图像上画出来&#xff0c;都需要做点云3D点坐标到图像像素坐标的转换计算&#xff0c;也就是LiDAR 3D坐标转像素坐标。 看了网上一些文章都存在有错误或者…
阅读更多...
【Maven】一篇带你了解Maven项目管理工具

【Maven】一篇带你了解Maven项目管理工具

目录 项目管理工具Maven初识Maven什么是Maven为什么使用MavenMaven功能什么是项目构建什么是依赖管理Maven应用场景Maven项目结构Maven特点Maven模型 Maven安装安装准备Maven安装目录分析环境变量配置 创建Maven项目通过IDEA创建手动创建手动引入依赖 配置Maven仓库Maven仓库概…
阅读更多...
工业物联网关-TCP透传

工业物联网关-TCP透传

TCP透传功能提供类似于DTU(Data Transmit Unit)的功能&#xff0c;用户在网络端使用TCP协议连接网关&#xff0c;与串口通道绑定&#xff0c;建立起TCP与串口的通道&#xff0c;网关相当于一个中转点。 菜单选择"数据上行-tcp透传"&#xff0c;查看当前透传通道列表&…
阅读更多...
最新文章

Copyright @ 2022~2023