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

单链表OJ题(3):合并两个有序链表、链表分割、链表的回文结构

目录

 一、合并两个有序链表

 二、链表分割

三、链表的回文结构


u解题的总体思路: 

合并两个有序链表:首先创建新链表的头节点哨兵位:本质上是占位子),为了减少一些判断情况,简化操作。然后我们再创建俩个指针分别指针两个单链表的头然后遍历比较,将两个指针指向节点的最小值接在新链表的后面

链表分割:创建两个新链表lessHead和greatHead一个存储原链表中小于x的节点,一个存储其他的节点,我们按顺序遍历原链表:当循环结束后,我们将存储小于x的节点的新链表lessHead接在另一个新链表greatHead的前面

链表的回文结构:我们利用前面OJ题中的方法,找中间节点(快慢指针),反转链表(三指针法)解这道题,我们找到中间节点后,将中间节点后面的节点的指向反转,然后我们遍历这个反转后的链表与原链表比较,看是否满足条件。

 一、合并两个有序链表

步骤1:

我们新建一个链表,初始化NewHead,NewTail三个指针都指向头节点NewList,然后,我们创建指针l1,l2分别指向list1和list2.

步骤2:当l1和l2指向的节点都不为NULL,循环遍历节点将最小值的节点接在新链表的后面,然后NewTail指向新链表的最后的节点位置上

 

步骤3:

我们将l1和l2指向链表节点不为NULL的接在NewTail的next域上,就完成了合并操作。 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode *l1 = list1,*l2 = list2;      ListNode *NewList = (ListNode*)malloc(sizeof(ListNode));    //创建头节点ListNode * NewHead, *NewTail; NewHead = NewTail = NewList;    //初始化俩个指针都指向新链表//l1 和 l2 当前节点都不为NULL,遍历while(l1 && l2){if(l1->val < l2->val){NewTail->next = l1;l1 = l1->next;     //l1往后走}else{NewTail->next = l2;l2 = l2->next;     //l2往后走}NewTail = NewTail->next;     //更新NewTail 指向当前新插入的节点}//两者有一个为NULL(不可能同时为NULL)if(l1!=NULL){NewTail->next=l1;}else{NewTail->next=l2;}return NewList->next;
}

 二、链表分割

 步骤1:

我们首先创建两个新的链表,lessHead存储节点值< x的节点greatHead存储节点值>= x的节点。

步骤2:

我们循环原链表,将每个节点按照判断接在各自的新链表中。

步骤3:

我们将lessHead的lessTail的next域接在greatHead的next前面,这样我们就实现了两个新链表的拼接.(注意:最后要将greatTail的next域置为NULL,防止死循环)

 

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <functional>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode *pcur = pHead;//创建俩个头节点,分别存储小节点,和大节点ListNode *lessHead = (ListNode*)malloc(sizeof(ListNode));ListNode *lessTail = lessHead;ListNode *greatHead =  (ListNode*)malloc(sizeof(ListNode));ListNode *greatTail = greatHead;//循环遍历原链表中的每个节点while(pcur){if(pcur->val < x){lessTail->next = pcur;lessTail = lessTail->next;     //尾指针后移当新插入的节点 }else{greatTail->next = pcur;greatTail = greatTail->next;    //尾节点后移到新插入的节点}pcur = pcur->next;}//拼接两个新链表,将lessHead接入到greatHead后面lessTail->next = greatHead->next;greatTail->next = NULL;     //将最后的节点next域置为NULLreturn lessHead->next;}
};

三、链表的回文结构

 步骤1:

我们首先写出找中间节点的函数middleNode,和反转链表的函数reverseList找到中间节点,然后,将中间节点后面的链表反转。(这两个函数在上个文章中详细讲解过,这里不再重点讲述

 步骤2:

反转以mid为头节点的链表。 

从这里可以看出我们的链表变成了俩个部分,然后我们遍历这两个链表比较各自节点的值是否相等相等说明我们原链表就是回文链表

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://反转链表ListNode* reverseList(ListNode* head){ListNode*n1,*n2,*n3;n1 = NULL;n2 = head;if(n2==NULL){return NULL;}n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}return n1;}//找中间节点ListNode* middleNode(ListNode* head){if(head==NULL){return NULL;}ListNode *slow,*fast;slow = fast = head;while(fast && fast->next){slow = slow->next;    //slow走一步fast = fast->next->next;    //fast走两步}return slow;}bool chkPalindrome(ListNode* A) {ListNode*phead = A;ListNode*mid = middleNode(A);    //找中间节点ListNode*pcur = reverseList(mid);   //反转以中间节点为头的后面的节点while(pcur){if(pcur->val != phead->val){return false;}pcur = pcur->next;phead = phead->next;}//循环正常结束,返回truereturn true;}
};

相关文章:

单链表OJ题(3):合并两个有序链表、链表分割、链表的回文结构

目录 一、合并两个有序链表 二、链表分割 三、链表的回文结构 u解题的总体思路&#xff1a; 合并两个有序链表&#xff1a;首先创建新链表的头节点&#xff08;哨兵位&#xff1a;本质上是占位子&#xff09;&#xff0c;为了减少一些判断情况&#xff0c;简化操作。然后我们…...

研究了100个小绿书十万加之后,我们发现2024小绿书独家秘籍就是:在于“先抄后超,持续出摊,量大管饱”!

小绿书作为今年最大的红利&#xff0c;很多人已经吃到了螃蟹。看——&#xff1a; 今天我们总结了100个10万爆款&#xff0c;我们发现要在这个平台上脱颖而出&#xff0c;找到属于自己的方法尤为重要。在这里分享一个主题——小绿书的秘诀就是“先抄后超&#xff0c;持续出摊”…...

Java 中 HashMap集合使用

目录 一. HashMap概述 二. HashMap特点 三. HashMap构造方法 四. HashMap的常用方法 五. 使用注意事项 六. 代码示例 一. HashMap概述 HashMap 是 Java 中的一个非常重要的类&#xff0c;它实现了 Map 接口&#xff0c;用于存储键值对&#xff08;key-value pairs&#…...

#渗透测试#SRC漏洞挖掘# 信息收集-Shodan进阶之Mongodb未授权访问

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…...

平台化运营公司如何在创业市场招商

在当今商业环境中&#xff0c;平台化运营的公司正成为推动经济发展的重要力量。对于这类公司而言&#xff0c;在创业市场招商意义重大。 平台化运营公司具有独特特点&#xff1a;通过搭建开放共享平台连接供需双方&#xff0c;实现资源优化配置与价值创造。比如电子商务平台、社…...

飞书API-获取tenant_access_token

1.在飞书工作台创建应用&#xff0c;跳到开发者后台&#xff0c;选创建企业自建应用 2.设置并发布应用 必须要发布应用才可以开始使用了&#xff01;&#xff01;&#xff01; 3.调用获取token的API 参考链接&#xff1a; 开发文档 - 飞书开放平台https://open.feishu.cn/do…...

(新)docker desktop镜像迁移

背景 docker desktop默认安装在系统c盘&#xff0c;久而久之随着镜像拉取的越多&#xff0c;系统盘占用则越来越大。现有的网络资源关于docker desktop迁移都是旧版本的&#xff0c;即4.30版本之前。在4.30版本及以后&#xff0c;在运行wsl -l -v时只有docker-desktop只有这一项…...

单向函数、单向陷门函数、困难问题

1、单向函数 设函数 yf(x) &#xff0c; 对于给定的x&#xff0c;计算出y很容易&#xff1b;对于给定的y&#xff0c;计算出x很难。 2、单向陷门函数 设函数 yf(x) &#xff0c;且f有陷门&#xff0c; 对于给定的x&#xff0c;计算出y很容易&#xff1b;对于给定的y&#…...

MYSQL 小猫钓鱼 - 猫王争霸之〈主从设计〉

在美丽的森林中&#xff0c;小猫们的钓鱼大赛依旧热闹非凡&#xff0c;而 “猫王争霸” 的竞争也越来越激烈。随着时间的推移&#xff0c;越来越多的动物们开始关注这场有趣的比赛&#xff0c;对鱼表数据的查询请求也急剧增加。 一、请求压力剧增 花猫看着鱼表发愁道&#xf…...

arcgis坐标系问题

2000数据框的工程只能打开2000坐标系的矢量数据和栅格数据&#xff08;影像图&#xff09;&#xff0c;如果打开80的数据则会投影错误&#xff0c;出现较大偏差。 解决方案&#xff1a;80数据框打开80数据&#xff0c;2000数据库打开2000数据。...

ubuntu 24.04中安装 Easyconnect,并解决版本与服务器不匹配问题

下载安装包 下载地址 https://software.openkylin.top/openkylin/yangtze/pool/all/ 页面搜索 easyconnect 选择 easyconnect_7.6.7.3.0_amd64.deb安装 sudo dpkg --install easyconnect_7.6.7.3.0_amd64.deb卸载 sudo dpkg --remove easyconnect出现的问题 安装以后第…...

【软考】RUP相关考点总结

RUP&#xff0c;是一个重量级过程&#xff0c;提供一个在线指导&#xff0c;为所有方面提供指导方针。 关于RUP&#xff08;统一软件开发过程&#xff09;的9个核心工作流&#xff0c;如果考试中出现&#xff0c;可能会以以下几种方式进行考察&#xff1a; 定义和描述&#xff…...

PostgreSQL 删除角色

我们在使用 PostgreSQL 数据库的时候&#xff0c;经常会遇到这样的场景&#xff0c;就是某个角色&#xff0c;现在不需要了&#xff0c;我们需要删除。但是在删除的时候又提示你无法删除角色。下面看一下具体的情况。 DROP USER cloud_readonly > ERROR: role "cloud…...

华为HCIP —— QinQ技术实验配置

一、QinQ的概述 1.1QinQ的概念 QinQ&#xff08;802.1Q in 802.1Q&#xff09;技术是一项扩展VLAN空间的技术&#xff0c;通过在原有的802.1Q报文基础上再增加一层802.1Q的Tag来实现。 1.2QinQ封装结构 QinQ封装报文是在无标签的以太网数据帧的源MAC地址字段后面加上两个VL…...

全网最简单的GraphRAG讲解,包你懂

一、什么是 GraphRAG&#xff1f; GraphRAG&#xff08;基于图的检索增强生成&#xff09;是在传统 RAG 方法的基础上&#xff0c;引入了图数据结构的新型方法。它利用大语言模型的强大自然语言理解能力&#xff0c;从非结构化文本中抽取实体和关系&#xff0c;构建知识图谱&a…...

rust 压缩解压库flate2保姆级教程

前言 flate2 是 Rust 中用于处理 gzip 和其他压缩格式的库。以下是 flate2 的主要 API 和用法说明。 依赖添加 在你的 Cargo.toml 中添加依赖&#xff1a; [dependencies] flate2 "1.0.34"主要模块 flate2::write&#xff1a;用于压缩数据的写入器。flate2::re…...

秒杀优化(异步秒杀,基于redis-stream实现消息队列)

目录 秒杀优化一&#xff1a;异步秒杀1&#xff1a;思路2&#xff1a;实现 二&#xff1a;redis实现消息队列1&#xff1a;什么是消息队列2&#xff1a;基于list结构实现消息队列3&#xff1a;基于pubsub实现消息队列4&#xff1a;基于stream实现消息队列5&#xff1a;stream的…...

Node.js——fs模块-文件读取

1、文件读取&#xff1a;通过程序从文件中去除其中的数据 2、方法 方法 说明 readFile 异步读取 readFileSync 同步读取 createReadStrean 流式读取 3、readFile 异步读取 语法&#xff1a; 本文的分享到此结束&#xff0c;欢迎大家评论区一同讨论学习&#xff0c;下一…...

深入理解 ZooKeeper:分布式协调服务的核心与应用

一、引言 随着互联网技术的飞速发展&#xff0c;分布式系统的规模和复杂性不断增加。在分布式环境中&#xff0c;各个节点之间需要进行高效的协调和通信&#xff0c;以确保系统的正常运行。ZooKeeper 正是为了解决分布式系统中的协调问题而诞生的一款开源软件。它提供了一种简单…...

你竟然还不了解 LDAP?

目录 什么是 LDAP LDAP 的工作原理 LDAP 的数据模型 LDAP 操作 LDAP 的使用场景 常见的 LDAP 服务器 小结 什么是 LDAP LDAP&#xff08;Lightweight Directory Access Protocol&#xff0c;轻量级目录访问协议&#xff09;是用于访问和管理目录服务的一种开放协议&…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...