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

反转链表相关的练习(下)

目录

一、回文链表

二、 重排链表

三、旋转链表



一、回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

示例 1

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

输出:true

示例 2

 输入:head = [1,2]

输出:false

提示

  • 链表中节点数目在范围[1, 10^5]

  • 0 <= Node.val <= 9

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

代码实现

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast != NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}
​
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pre = NULL;struct ListNode* cur = head;while (cur != NULL){struct ListNode* after = cur->next;cur->next = pre;pre = cur;cur = after;}return pre;
}
​
bool isPalindrome(struct ListNode* head)
{// 1. 找到中间结点,如果有两个中间结点,则找到第二个中间结点struct ListNode* mid = middleNode(head);// 2. 从中间结点开始,对后半段进行反转struct ListNode* rightHead = reverseList(mid);// 3. 进行前半段和后半段的比较struct ListNode* leftCur = head;struct ListNode* rightCur = rightHead;while (rightCur != NULL){if (leftCur->val != rightCur->val){return false;}leftCur = leftCur->next;rightCur = rightCur->next;}return true;
}

回文结构是一个生物学名词。双链 DNA 中含有的两个结构相同、方向相反的序列称为回文结构,每条单链以任一方向阅读时都与另一条链以相反方向阅读时的序列是一致的

palindrome n. 回文结构;回文序列 ==> 牛津:a word or phrase that reads the same backwards as forwards, for example madam.


二、 重排链表

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1

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

示例 2

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

输出:[1,5,2,4,3]

提示

  • 链表的长度范围为 [1, 5 * 10^4]

  • 1 <= node.val <= 1000

代码实现

struct ListNode* middleNode(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* reverseList(struct ListNode* head)
{struct ListNode* pre = NULL;struct ListNode* cur = head;while (cur != NULL){struct ListNode* after = cur->next;cur->next = pre;pre = cur;cur = after;}return pre;
}
​
void reorderList(struct ListNode* head)
{// 1. 找到中间结点,如果有两个中间结点,则找到第二个中间结点struct ListNode* mid = middleNode(head);// 2. 从中间结点开始,对后半段进行反转struct ListNode* rightHead = reverseList(mid);// 3. 重排链表struct ListNode* leftCur = head;struct ListNode* rightCur = rightHead;while (rightCur->next != NULL){struct ListNode* leftAfter = leftCur->next;struct ListNode* rightAfter = rightCur->next;leftCur->next = rightCur;rightCur->next = leftAfter;leftCur = leftAfter;rightCur = rightAfter;}
}

图解示例二

 

三、旋转链表

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1

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

输出:[4,5,1,2,3]

示例 2

 输入:head = [0,1,2], k = 4

输出:[2,0,1]

提示

  • 链表中节点的数目在范围 [0, 500]

  • -100 <= Node.val <= 100

  • 0 <= k <= 2 * 109

代码实现

struct ListNode* rotateRight(struct ListNode* head, int k)
{if (head == NULL){return NULL;}// 1. 找到链表的尾结点,并计算它的长度struct ListNode* tail = head;int len = 1;while (tail->next != NULL){++len;tail = tail->next;}// 2. 找到倒数第 (k % len + 1) 个结点k %= len;if (k == 0){return head;}struct ListNode* pre = head;for (int i = 0; i < len - k - 1; ++i){pre = pre->next;}// 3. 旋转链表tail->next = head;  // (1)head = pre->next;  // (2)pre->next = NULL;  // (3)return head;
}

相关文章:

反转链表相关的练习(下)

目录 一、回文链表 二、 重排链表 三、旋转链表 一、回文链表 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输…...

2.进程和线程

1.进程1.1 终止正常退出(自愿)出错退出(自愿)严重错误(非自愿)被其他进程杀死(非自愿)1.2 状态就绪态&#xff1a;可运行&#xff0c;但因为其他进程正在运行而暂时停止阻塞态&#xff1a;除非某种外部事件发生&#xff0c;否则进程不能运行1.3 实现一个进程在执行过程中可能被…...

C++回顾(十四)—— 函数模板

14.1 概述 所谓函数模板(function template)&#xff0c;实际上是建立一个通用函数&#xff0c;其函数类型和形参类型不具体指定&#xff0c;用一个虚拟的类型来代表。这个通用函数就称为函数模板。凡是函数体相同的函数都可以用这个模板来代替&#xff0c;不必定义多个函数&a…...

如何做好项目各干系人的管理及应对?

如何更好地识别、分析和管理项目关系人&#xff1f;主要有以下几个方面&#xff1a; 1、项目干系人的分析 一般对项目干系人的分析有2种方法&#xff0c; 方法一&#xff1a;权利&#xff08;影响&#xff09;&#xff0c;即对项目可以产生影响的人&#xff1b; 方法二&#xf…...

Elasticsearch使用系列-ES增删查改基本操作+ik分词

一、安装可视化工具KibanaES是一个NoSql数据库应用。和其他数据库一样&#xff0c;我们为了方便操作查看它&#xff0c;需要安装一个可视化工具 Kibana。官网&#xff1a;https://www.elastic.co/cn/downloads/kibana和前面安装ES一样&#xff0c;选中对应的环境下载&#xff0…...

07-PL/SQL基础(if语句,case语句,循环语句)

本章主要内容&#xff1a; 1.PL/SQL的基本构成&#xff1a;declare,begin,exception,end; 2.结构控制语句:IF语句,CASE语句 3.循环结构&#xff1a;loop循环&#xff0c;for loop循环&#xff0c;while loop循环 PL/SQL的基本构成 特点 PL/SQL语言是SQL语言的扩展&#xff…...

信捷 XDH Ethercat A_VELMOVE

本文描述信捷 EthercatA_VELMOVE指令&#xff0c;以设定的速度持续运行 上图中&#xff0c;在M100的上升沿&#xff0c;执行A_VELMOVE指令。A_VELMOVE HD100 D100 M101 K0HD100输入参数起始地址 &#xff0c;HD118输入参数末尾地址HD100~HD103,双精度浮点数&#xff08;64位&am…...

【专项训练】分治、回溯

分治、回溯其实就是递归,只是是递归的一个细分,是一种特殊的递归 碰到一个题目,你就找他的重复性 最近重复性:根据重复性怎么构造以及如何分解,包括:分治、回溯 最优重复性:动态规划 本质:找重复性、分解问题、组合子问题的结果 回溯:试错! 50. Pow(x, n) https:…...

Linux上安装配置ZooKeeper

Linux上安装配置ZooKeeper 下载压缩文件 将压缩文件拷贝到指定目录下 执行命令 tar -zxvf [apache-zookeeper-3.5.7-bin.tar.gz] -C [/opt/module/]注&#xff1a;第一个括号里面是压缩文件名称&#xff0c;第二个括号里面是解压到指定的目录 进入到解压后的文件夹当中&am…...

idea leetcode插件无法登录

em 2022某天 leetcode-cn.com 改为了 leetcode.cn so , 如果是版本比较老idea leetcode插件, 就无法使用了. 因为用的旧域名 先说解决办法: 2.0 先把旧版本卸载了 2.1 ideaplugin官网找到本地idea版本下可安装的最高版本的leetcode.cn 假设是 leetcode-editor-6.9.zip 2.2 下…...

VR会议不断升级,为商务会谈打造云端洽谈服务!

VR会议不断升级&#xff0c;为商务会谈打造云端洽谈服务。在商务合作中&#xff0c;对客户需求的理解以及与客户讲解方案都需要建立在一个有效的沟通上&#xff0c;因此VR会议的用武之地就有了&#xff0c;以VR全景技术为核心&#xff0c;通过同屏互动和全景通信技术&#xff0…...

Ubuntu系统开机自动挂载NTFS硬盘【超实用】

由于跑深度学习实验(图像分割)f非常消耗内存&#xff0c;系统盘sda1内存小&#xff0c;配置了一个大容量得出NTFS机械盘&#xff0c;网上招了一些资料如何挂在&#xff0c;但是每次开机得手动挂载一遍才能使用硬盘&#xff0c;非常不方便&#xff0c;还容易造成数据丢失。 Step…...

淘宝十年资深架构师吐血总结淘宝的数据库架构设计和采用的技术手段。

淘宝十年资深架构师吐血总结淘宝的数据库架构设计和采用的技术手段。 文章目录淘宝十年资深架构师吐血总结淘宝的数据库架构设计和采用的技术手段。本文导读1.分库分表2.数据冗余3.异步复制4.读写分离总结本文导读 淘宝的数据库架构设计采用了分布式数据库技术&#xff0c;通过…...

训练自己的GPT2-Chinese模型

文章目录效果抢先看准备工作环境搭建创建虚拟环境训练&预测项目结构模型预测续写训练模型遇到的问题及解决办法显存不足生成的内容一样文末效果抢先看 准备工作 从GitHub上拉去项目到本地&#xff0c;准备已训练好的模型百度网盘&#xff1a;提取码【9dvu】。 gpt2对联训…...

springcloud3 fegin服务超时的配置和日志级别的配置2

一 fegin的概述 1.1 fegin的默认超时时间 默认fegin客户端只等待1秒钟&#xff0c;超过1秒钟&#xff0c;直接会返回错误。 1.2 架构图 1.2.1 说明 1.2.2 启动操作 1.先启动9001,9002 eureka 2.启动9003 服务提供者 3.启动9006消费者 1.3 情况验证 1.3.1 正常默认情…...

华为机试 HJ48 从单向链表中删除指定值的节点

题目链接 描述 输入一个单向链表和一个节点的值&#xff0c;从单向链表中删除等于该值的节点&#xff0c;删除后如果链表中无节点则返回空指针。 链表的值不能重复。 构造过程&#xff0c;例如输入一行数据为: 6 2 1 2 3 2 5 1 4 5 7 2 2 则第一个参数6表示输入总共6个节点&a…...

华为机试 HJ1 字符串最后一个单词的长度

华为机试 HJ1 字符串最后一个单词的长度 文章目录华为机试 HJ1 字符串最后一个单词的长度一、题目描述二、方法一 Java lastIndexOf() 方法三、方法二 Java split()方法使用Java的lastIndexOf()和split()解决求取方法字符串最后一个单词的长度的问题 一、题目描述 计算字符串最…...

从入门到精通MongoDB数据库系列之二:深入了解MongoDB基本概念文档、集合、数据库、数据类型、MongoDB shell

从入门到精通MongoDB数据库系列之二:深入了解MongoDB基本概念文档、集合、数据库、数据类型、MongoDB shell 一、MongoDB基本概念二、文档三、集合1.动态模式2.命名四、数据库五、MongoDB shell1.运行shell2.连接远程MongoDB数据库3.shell中的基本操作六、数据类型1.基本数据类…...

前端实用技巧,JS压缩、美化、JS混淆加密

作为一名前端开发者&#xff0c;关注JavaScript代码的安全性和隐私性&#xff0c;或者需要对JavaScript代码进行美化、格式化、压缩等操作&#xff0c;帮助你提高开发效率和代码质量&#xff0c;利用一个好的工具非常重要。 如果不想让自己的代码被恶意篡改和盗用&#xff0c;作…...

synchronized轻量级锁优化

synchronized优化轻量级锁 使用场景 如果一个对象虽然有多个线程访问&#xff0c;但多线程访问时间是错开的&#xff0c;也就是没有竞争&#xff0c;那么可以使用轻量级锁优化&#xff1b; 原理 1、每个线程的栈帧中有锁记录 包括&#xff1a;记录锁对象的地址Object refer…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...