当前位置: 首页 > news >正文

【数据结构】链表OJ(二)

Yan-英杰的博客 

 悟已往之不谏 知来者之可追


目录

一、反转链表

二、合并两个有序链表

三、链表分割

四、链表的回文结构


一、反转链表

 

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

方法一:

        代码解析:   

struct ListNode* reverseList(struct ListNode* head){if(head == NULL){return NULL;}struct 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;}return n1;
}

        画图解析:

                

        注:该题使用到了三指针

 方法二:

        代码解析:

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head,*newhead = NULL;while(cur){struct ListNode* next = cur->next;//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}

        画图解析:

 此方法采用头插方式

二、合并两个有序链表

 

        将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

        示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

 示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100
    l1 和 l2 均按 非递减顺序 排列

代码解析:

        

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* cur1 = list1,*cur2 = list2;struct ListNode* head = NULL,*tail = NULL;while(cur1 && cur2){if(cur1->val < cur2->val){if(head == NULL){head = tail = cur1;}else{tail->next = cur1;tail = tail->next;}cur1 = cur1->next;}else{if(head == NULL){head = tail = cur2;}else{tail->next = cur2;tail = tail->next;}cur2 = cur2->next;}}if(cur1){tail->next = cur1;}if(cur2){tail->next = cur2;}return head;
}

画图解析:
        

三、链表分割

 

        描述

        现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

        思路:

      小于尾插到一个链表,大于等于尾插到另一个链表,再将两个链表链接起来

        代码解析:

                

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* gGurad,*gTail,*lGuard,*lTail;gGurad = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));gTail->next = lTail->next = NULL;struct ListNode* cur = pHead;while(cur){if(cur->val < x){lTail->next = cur;lTail = lTail->next;}else{gTail->next = cur;gTail = gTail->next;}cur= cur->next;}lTail->next = gGurad->next;gTail->next =NULL;pHead = lGuard->next;free(gGurad);free(lGuard);return pHead;}
};

        画图解析:

                        

 

         此题我们需要用到哨兵位的头节点

四、链表的回文结构

 

        描述

        对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

        给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

        测试样例:

1->2->2->1
返回:true

        代码解析:

                                

//查找中间节点
struct ListNode* Mid(struct ListNode* Head) {struct ListNode* slow = Head;struct ListNode* fast = Head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}//链表逆置
struct ListNode* reverse(struct ListNode* Head)
{struct ListNode* cur = Head;struct ListNode* phead = NULL;while(cur){struct ListNode* next = cur->next;cur->next = phead;phead = cur;cur = next;}return phead;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* MidList = Mid(A);struct ListNode* ReList = reverse(MidList);struct ListNode* pphead = A;struct ListNode* ppheadR = ReList;while(pphead && ppheadR){if(pphead->val != ppheadR->val){return false;}else{pphead = pphead->next;ppheadR = ppheadR->next;}}return true;}
};

        画图解析:

                

 

相关文章:

【数据结构】链表OJ(二)

Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表 二、合并两个有序链表 三、链表分割 四、链表的回文结构 一、反转链表 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xf…...

Linux系统搭建FTP服务器

安装vsftpdyum -y install vsftpd添加FTP用户方式1、添加只允许通过ftp访问的用户useradd -d /home/ftp ftp_user #-d指定用户登录时的启始目录方式2、允许用户登录操作系统usermod -d /home/ftp -s /bin/bash ftp_user #-s指定用户登入后所使用的shell设置用户登录密码passwd …...

MySQL数据同步到 Redis 缓存的几种方法

1 Mysql查完数据&#xff0c;再同步写入到Redis中缺点1&#xff1a;会对接口造成延迟&#xff0c;因为同步写入redis本身就有延迟&#xff0c;并且还要做重试&#xff0c;如果redis写入失败&#xff0c;还需要重试&#xff0c;那就更费时间了。缺点2&#xff1a;不解耦&#xf…...

2023年网络安全比赛--CMS网站渗透中职组(超详细)

一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.使用渗透机对服务器信息收集,并将服务器中网站服务端口号作为flag提交; 2.使用渗透机对服务器信息收集,将网站的名称作为flag提交; 3.使用渗透机对服务器渗透,将可渗透页面的名称作为flag提交; 4.使用渗透机对服务器渗透,…...

【蓝桥杯集训·每日一题】AcWing 4309. 消灭老鼠

文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最大公约数一、题目 1、原题链接 4309. 消灭老鼠 2、题目描述 约翰的农场可以看作一个二维平面。 农场中有 n 个老鼠&#xff0c;在毁坏着农田。 第 i 个老鼠的位置坐标为…...

FPGA实现CSI-2 解码MIPI视频 2line 720P分辨率 OV5647采集 提供工程源码和技术支持

目录1、前言2、Xilinx官方主推的MIPI解码方案3、纯Vhdl方案解码MIPI4、vivado工程介绍5、上板调试验证6、福利&#xff1a;工程代码的获取1、前言 FPGA图像采集领域目前协议最复杂、技术难度最高的应该就是MIPI协议了&#xff0c;MIPI解码难度之高&#xff0c;令无数英雄竞折腰…...

JS面试题收集(持续更新好中...)

1.JavaScript 中的垃圾回收机制 定义&#xff1a;指一块被分配的内存既不能使用&#xff0c;又不能回收&#xff0c;直到浏览器进程结束。 JavaScript在创建对象时会为它们分配内存&#xff0c;不再使用时会自动释放内存&#xff0c;这个过程称为垃圾收集。 四种常见的内存泄…...

2023携程面试题

Java I/O 面试前需要准备&#xff1a; 1. Java 八股文&#xff1a;了解常考的题型和回答思路&#xff1b; 2. 算法&#xff1a;刷 100-200 道题&#xff0c;记住刷题最重要的是要理解其思想&#xff0c;不要死记硬背&#xff0c;碰上原题很难&#xff0c;但 大多数的解题思…...

CANoe中使用CAPL函数接口调用Vflash文件

&#x1f345; 我是蚂蚁小兵&#xff0c;专注于车载诊断领域&#xff0c;尤其擅长于对CANoe工具的使用&#x1f345; 寻找组织 &#xff0c;答疑解惑&#xff0c;摸鱼聊天&#xff0c;博客源码&#xff0c;点击加入&#x1f449;【相亲相爱一家人】&#x1f345; 玩转CANoe&…...

三天吃透计算机网络面试八股文

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…...

shp数据添加wkt字段并导出成csv,leaflet绘制使用

准备的东西&#xff1a;软件2跟软件3具体怎么有这些软件需要自行百度postgresql postgis相关 1.shp数据 2.软件2 3.软件3 1.数据导入 首先你得有软件2的数据库&#xff0c;即postgresql数据库&#xff0c;然后通过postgis的插件进行连接并导入数据&#xff0c; 导入数据…...

Java——二叉树的最近公共祖先及二叉搜索树介绍

目录 二叉树的最近公共祖先 题目 思路一&#xff1a;如果给定的是一颗二叉搜索树&#xff0c; 思路二&#xff1a;假设是孩子双亲表示法 二叉搜索树 定义Node类 查找 删除 插入 二叉树的最近公共祖先 题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百…...

Stable Diffusion加chilloutmixni真人图片生成模型,AI绘图杀疯了

上期图文教程,我们分享过AI绘图大模型Stable Diffusion以及中文版本文心AI绘画大模型的基础知识以及代码实现,截至到目前为止。Stable Diffusion模型已经更新到了V2.1版本,其文生图大模型也越来越火,其在2022年底,由AI绘制的图片被荣为国际大奖,让大家对AI绘画大模型也越…...

Matplotlib 绘图实用大全

本文只介绍最简单基本的画图方法 预设 要想画出来的图有些逼格&#xff0c;首先应该进行如下设置 plt.rcParams[font.sans-serif][SimHei] #画图时显示中文字体 plt.rcParams[axes.unicode_minus] False #防止因修改成中文字符&#xff0c;导致某些 unicode 字符不能…...

MyBatis源码用了哪些设计模式?

MyBatis源码用了哪些设计模式&#xff1f;前言一、创建型模式工厂模式单例模式建造者模式二、结构型模式适配器模式代理模式组合模式装饰器模式三、行为型模式模板模式策略模式迭代器模式总结前言 在 MyBatis 的两万多行的框架源码中&#xff0c;使用了大量的设计模式对工程架…...

【16.整数转罗马数字】

罗马数字包含以下七种字符&#xff1a; I&#xff0c; V&#xff0c; X&#xff0c; L&#xff0c;C&#xff0c;D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例…...

前端小技巧

1.html 1.1 网站自动刷新 应用场景&#xff1a; 网页定期自动刷新&#xff08;现在基本淘汰了&#xff0c;采用ajax&#xff09;&#xff1b;自动跳转到指定页面&#xff0c;这个自动跳转的好处就是不需要JS调用&#xff0c;属于纯html网页自动跳转 v7-网站自动刷新 你可以…...

Servlet2.0

文章目录更方便的部署方式安装插件使用插件验证程序常见访问出错的解决方案404错误405错误500错误空白页面无法访问此网站在文章 TomcatServlet初识中&#xff0c;我们通过七个大的步骤才可以完成一个简单的Servlet程序&#xff0c;这个过程无疑是非常繁琐的&#xff0c;那么我…...

【c++】继承

目录 一、继承的表现 子类对父类成员的访问权限 二、父类与子类之间的相互赋值 三、继承的作用域 如果是父类和子类构成隐藏呢&#xff1f; 四、子类的成员函数怎么写 1.default构造函数 2.析构函数 所以析构函数不需要我们显式调用。 五、继承与友元函数 六、继承与静…...

minio安装配置和使用(二)客户端安装

安装minio客户端mcli 命令如下&#xff1a; dnf install https://dl.minio.org.cn/client/mc/release/linux-amd64/mcli-20230128202938.0.0.x86_64.rpm 安装完成&#xff0c;在/usr/local/bin/下新增了mcli命令 mcli是对minio进行管理的命令。功能丰富&#xff0c; 基本格式…...

YOLO X Layout实战:从扫描PDF中自动提取标题与表格的Python实现

办公室最头疼的工作之一就是处理扫描版PDF&#xff1a;不管是合同、审计报告、论文还是发票&#xff0c;扫描版的PDF都是图片&#xff0c;没法复制文本&#xff0c;要提取里面的标题、目录、表格&#xff0c;只能手动敲&#xff0c;几十页的PDF要花几个小时&#xff0c;特别浪费…...

华为OD面试-Java、C++、Pyhton等多语言实现-目录

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;华为OD面试 文章目录一、&#x1f340;2023A卷二、&#x1f340;2023B卷一、&#x1…...

企业网络改造不求人:手把手教你深信服防火墙旁挂部署(含NQA配置避坑指南)

企业级防火墙旁挂部署实战&#xff1a;深信服设备零基础配置指南 当企业网络规模逐步扩大&#xff0c;业务系统日益复杂&#xff0c;网络安全防护往往成为IT运维团队最头疼的问题之一。传统防火墙部署通常需要对现有网络架构进行大规模调整&#xff0c;不仅实施周期长&#xff…...

KF32A150开发第一步:手把手教你用KF32 IDE导入、编译和烧录第一个工程

KF32A150开发实战&#xff1a;从零完成工程导入到烧录的全流程指南 第一次接触芯旺微KF32系列MCU时&#xff0c;面对陌生的开发环境和工具链&#xff0c;很多开发者都会感到无从下手。本文将带你一步步完成KF32A150开发板的第一个程序烧录&#xff0c;涵盖工程导入、编译配置到…...

自媒体人利器:OpenClaw+百川2-13B自动生成短视频脚本

自媒体人利器&#xff1a;OpenClaw百川2-13B自动生成短视频脚本 1. 为什么需要自动化脚本生成工具 作为一个每天需要产出3-5条短视频的自媒体创作者&#xff0c;我经常陷入创意枯竭和重复劳动的困境。传统的工作流程需要手动搜索热点、构思脚本、撰写分镜&#xff0c;这个过程…...

MOS管技术详解:从基础到工程应用

MOS管技术详解&#xff1a;从基础原理到工程应用1. MOS管基础概念与分类1.1 场效应管基本类型场效应管(FET)主要分为两大类型&#xff1a;结型场效应管(JFET)&#xff1a;Junction Field-Effect Transistor金属氧化物半导体场效应管(MOSFET)&#xff1a;Metal-Oxide-Semiconduc…...

嵌入式开发问题复现与调试技巧

嵌入式开发常见问题及解决方法1. 问题复现方法稳定复现问题是解决嵌入式系统故障的首要步骤。根据问题特性&#xff0c;可采用以下三种复现方法&#xff1a;1.1 模拟复现条件对于依赖特定外部条件的问题&#xff0c;最直接的复现方式是精确还原问题发生时的环境参数。工程实践中…...

为 GraphRAG 准备语料库

经典 RAG 专注于找到正确的段落&#xff0c;而 GraphRAG 帮助你看到段落、实体和主题在整个文档集合中是如何连接的。原始 GraphRAG 论文指出&#xff0c;标准 RAG 常常在处理宽泛问题时遇到困难&#xff0c;比如"这个数据集中的主要主题是什么&#xff1f;"为了解决…...

SSRF漏洞实战:用Pikachu靶场玩转curl_exec和file_get_contents攻击链

SSRF漏洞攻防实战&#xff1a;从Pikachu靶场到企业级防御体系 当你在浏览器地址栏输入?urlfile:///etc/passwd并成功读取系统文件时&#xff0c;服务器就像一位过于热心的管家&#xff0c;将保险柜钥匙交给了陌生人。这就是SSRF&#xff08;Server-Side Request Forgery&#…...

java毕业设计基于springboot+vue的考研在线学习平台

前言 Spring Boot考研在线学习平台基于Spring Boot框架开发&#xff0c;充分利用了Spring Boot的自动配置和高效开发特性。这使得平台的搭建和开发过程更加简化&#xff0c;同时也保证了平台的稳定性和可靠性。此外&#xff0c;平台还采用了前后端分离 的架构&#xff0c;使得用…...