Leetcode算法题(链表的中间节点+返回倒数第k个节点+合并两个有序链表)

题目1:

本题力扣链接:https://leetcode.cn/problems/middle-of-the-linked-list/solutions/164351/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/

思路1:单指针法

首先我们对链表进行遍历,记录链表的总长度N,再进行遍历原链表,返回刚跳出循环大于N/2时,对应的链表节点,即为中间节点。

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pcur=head;if(head==NULL){return head;}int count=0;while(pcur){count++;pcur=pcur->next;}pcur=head;int k=0;while(k<count/2){k++;pcur=pcur->next;}return pcur;
}

思路2:快慢指针法

typedef struct ListNode ListNode ;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;}

场景1:

场景二:

题目2:

OJ链接:

思路1:反转链表+遍历

先将原链表进行翻转,再将反转后的链表的头结点移动k-1位,最后直接返回此时节点的值。

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){//1. 先将原链表进行翻转//2. 再将反转后的链表的头结点移动k-1位ListNode* n1,*n2,*n3;n1=NULL,n2=head,n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}k=k-1;while(k--){n1=n1->next;}return n1->val;
}

复杂度分析:

时间复杂度:O(N),其中N为给定链表节点的数目。

空间复杂度:O(1)

思路2:遍历+挪动

先计算原链表的总长度s,再将原链表的头结点移动s-k位,返回此时节点对应的值。

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){ListNode* pcur=head;int s=0;while(pcur){s++;pcur=pcur->next;}int m=s-k;while(m--){head=head->next;}return head->val;}

复杂度分析:

时间复杂度:O(N),其中N为给定链表节点的数目。

空间复杂度:O(1)

题目3:

思路:遍历+尾插+比较

创建新的带头链表,依次遍历两个原链表,比较对应的值,尾插到新的链表尾部。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}ListNode* newlist,*newhead;newhead=newlist=(ListNode*)malloc(sizeof(ListNode));while (list1 && list2) {if (list1->val > list2->val) {newlist->next = list2;list2 = list2->next;} else {newlist->next = list1;list1 = list1->next;}newlist = newlist->next;}if (list1)newlist->next = list1;if (list2)newlist->next = list2;return newhead->next;
}

如果本文章对你有帮助,期待你的三连!!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信小程序毕业设计-学习资料库系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…

使用APEXSQL LOG解析sql server事务日志,进行审计与数据恢复

一 下载 https://download.csdn.net/download/sunke861/11449739 二 使用 解压安装包后&#xff0c;点击&#xff1a;ApexSQLLog.exe 2.1 连接数据库 连接要审计的数据库&#xff1a; 假如报错&#xff1a; 则点击ok关闭该窗口&#xff0c;然后点击左上方的New按钮&#xf…

平替ChatGPT的多模态智能体来了

在人工智能领域&#xff0c;多模态技术的融合与应用已成为推动技术革新的关键。今天&#xff0c;我们用智匠AI实现了完全由国产模型驱动的多模态智能体——智酱v0.1.0&#xff0c;它不仅能够媲美ChatGPT的多模态能力&#xff0c;更在联网搜索、图片识别、画图及图表生成等方面展…

Python进阶 2024/7/15

目录 文件的写入操作 打开文件 文件写入 内容刷新 文件的追加写入操作 打开文件 文件写入 内容刷新 a模式 练习 文件的写入操作 文件的访问模式要用 w 打开文件 f open( " D:\ACM\python.txt "," w ",encoding " UTF - 8") 文件写…

BL201分布式I/O耦合器连接Profinet网络

钡铼技术的BL201分布式I/O耦合器是一个用于Profinet网络的设备&#xff0c;用于连接远程输入/输出&#xff08;I/O&#xff09;设备到控制系统&#xff0c;如可编程逻辑控制器&#xff08;PLC&#xff09;&#xff0c;能够实现分布式的I/O连接和通信。 它支持标准Profinet IO …

Xilinx FPGA UltraScale SelectIO 接口逻辑资源

目录 1. 简介 2. Bank Overview 2.1 Diagram 2.2 IOB 2.3 Slice 2.4 Byte Group 2.5 I/O bank 示例 2.6 Pin Definition 2.7 数字控制阻抗(DCI) 2.8 SelectIO 管脚供电电压 2.8.1 VCCO 2.8.2 VREF 2.8.3 VCCAUX 2.8.4 VCCAUX_IO 2.8.5 VCCINT_IO 3. 总结 1. 简介…

mac电脑pdf合并,macpdf合并成一个pdf

在数字化办公和学习的今天&#xff0c;pdf文件因其跨平台兼容性强、格式稳定而成为了最受欢迎的文档格式之一。但随之而来的问题也接踵而至&#xff0c;如何将多个pdf文件合并为一个&#xff1f;这不仅关系到文档的整洁性&#xff0c;更是时间管理的重要环节。今天&#xff0c;…

Windows与Linux双机热备软件推荐

网络数据安全在如今信息化的时代越来越变得举足轻重&#xff0c;因此服务器维护和管理也成为企业健康稳定运营的一项重要工作。但实际情况是很多公司并没有配备专业的运维人员&#xff0c;一般都会通过一些管理软件维护或者主机托管给服务商。整理6款服务器的Windows与Linux双机…

大模型在证券公司智能客服领域的应用初探

在证券行业&#xff0c;智能客服已成为提升客户体验、提高服务效率以及扩大市场覆盖面的重要手段。智能客服不仅需要具备快速响应的能力&#xff0c;其应答还应能覆盖广泛的业务领域&#xff0c;且需具有较高的准确率。近年来&#xff0c;AI技术飞速发展&#xff0c;尤其是大规…

Android中元数据meta-data的使用

一 概述 meta-data&#xff08;元数据&#xff09;&#xff0c;主要用来定义一些组件相关的配置值。与String.xml只能暴露给内部不同&#xff0c;AndroidManifests.xml下的meta-data是对外界开放的&#xff0c;是向系统注册的信息&#xff0c;系统及外界是可以通过相关API获取…

数码暴龙机(电波暴龙机)彩色复刻版!!| 使用Python、PySide6、pixilart自制windows桌面宠物

一、前言 数码暴龙机&#xff08;电波暴龙机&#xff09;是万代公司发售的一系列与《数码兽》系列相关的液晶玩具商品。这些产品融合了养成和对战元素&#xff0c;为玩家提供了一种虚拟养成和战斗的娱乐体验。也是很多人的童年回忆。最近在B站刷到讲解暴龙通关的教程和视频&…

【Python】基础语法(函数、列表和元组、字典、文件)

。一、函数 1、函数是什么 编程中的函数和数学中的函数有一定的相似之处。 数学上的函数&#xff0c;比如 y sin x&#xff0c;x 取不同的值&#xff0c;y 就会得到不同的结果。 编程中的函数是一段可以被重复使用的代码片段。 &#xff08;1&#xff09;求数列的和&…

Flink Window 窗口【更新中】

Flink Window 窗口 在Flink流式计算中&#xff0c;最重要的转换就是窗口转换Window&#xff0c;在DataStream转换图中&#xff0c;可以发现处处都可以对DataStream进行窗口Window计算。 窗口&#xff08;window&#xff09;就是从 Streaming 到 Batch 的一个桥梁。窗口将无界流…

蓝桥杯14小白月赛题解

直接输出pi/ti,for遍历 #include <iostream> using namespace std; #define int long long int a,b,c ; double t1.00; signed main() {cin>>a;int an0;for(int i1;i<a;i){cin>>b>>c;if(t>c*1.00/b){tc*1.00/b;ani;} }cout<<an<<e…

云盘挂载 开机自动模拟 cmd- alist server

云盘挂载 开机自动模拟 cmd- alist server 打开Kimi智能助手, 网址:Kimi.ai - 帮你看更大的世界 (moonshot.cn) 问他: 帮我写一个vbs命令:在D:\sky目录下, 然后cmd, 进入命令行后, 输入 alist server 然后回车 这里 这个目录, 换成自己的 alist.exe所在目录 下面是我完善的示…

软考中级科目包含哪些?应该考哪个?

软考中级包含5个专业方向&#xff0c;分别是&#xff1a;计算机软件、计算机网络、计算机应用技术、信息系统、信息服务。这5个方向又对应15个软考中级科目。 信息系统包括&#xff1a;系统集成项目管理工程师、信息系统监理师、信息安全工程师、数据库系统工程师、信息系统管…

Linux C语言基础 day10

目录 学习目标&#xff1a; 学习内容&#xff1a; 1.指针指向数组 1.1 指针与数组的关系 1.2 指针与一维数组关系实现 1.2.1 指针与一维数组的关系 1.2.2 指针指向一维整型数组作为函数参数传递 课外作业&#xff1a; 学习目标&#xff1a; 一周掌握 C基础知识 学习内…

部署k8s 1.28.9版本

继上篇通过vagrant与virtualBox实现虚拟机的安装。笔者已经将原有的vmware版本的虚拟机卸载掉了。这个场景下&#xff0c;需要重新安装k8s 相关组件。由于之前写的一篇文章本身也没有截图。只有命令。所以趁着现在。写一篇&#xff0c;完整版带截图的步骤。现在行业这么卷。离…

PyMongo Sort 操作:提升你的数据查询效率

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

极狐Gitlab使用(2)

目录 1. Gitlab命令行修改管理员密码 2. Gitlab服务管理 3. 公司的开发代码提交处理流程 4. Gitlab 备份与恢复 数据备份 测试数据恢复 5. 邮箱配置 1. Gitlab命令行修改管理员密码 [roottty01 ~]# gitlab-rails console -e production # 启动GitLab的Rails控制…