算法通关村第二关|白银|链表反转拓展【持续更新】
1.指定区间反转
1.1 头插法:将区间内遍历到的结点插入到起始处之前。
public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 将pre移动到区间的前一位,pre.next指向每次遍历到的需要插入到起始处的结点for (int i = 0; i < left - 1; i++) {pre = pre.next;}// cur负责遍历ListNode cur = pre.next;// next存储遍历到的结点ListNode next;for (int i = 0; i < right - left; i++) {//存储遍历到的结点cur.nextnext = cur.next;//将cur.next向后移动,下次循环继续遍历cur.next = next.next;//让遍历到的结点指向起始处的结点next.next = pre.next;//pre指向新的起始处pre.next = next;}return dummyNode.next;
}
1.2 穿针引线法:找到需要裁切的地方,将子链表整体反转,然后再缝到切开的地方。
public ListNode reverseBetween(ListNode head, int left, int right){ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 找 left 结点的前一个结点for (int i = 0; i < left - 1; i++) {pre = pre.next;}// 找 right 结点ListNode rightNode = pre;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}// 切割子链表ListNode leftNode = pre.next;ListNode succ = rightNode.next;rightNode.next = null;// 反转链表reverseList(leftNode);// 拼接pre.next = rightNode;leftNode.next = succ;return dummyNode.next;
}
// 反转链表算法
public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while(curr != null){ListNode next = curr.next;// 这里对链表的结构进行了更改// 所以不需要返回值,但是上面的leftNode结构已经更改了curr.next = prev;prev = curr;curr = next;}return prev;}
}
2.两两交换链表中的节点
捋清楚成对交换结点时的指针指向即可。
public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;
}
3.单链表加1
3.1 基于栈实现。
public ListNode plusOne(ListNode head) {Stack<Integer> stack = new Stack();while (head != null) {stack.push(head.val);head = head.next;}int carry = 0;ListNode dummy = new ListNode(0);// 本题要加1,所以设置了adder为1int adder = 1;while (!stack.empty() || carry > 0) {int digit = stack.empty() ? 0 : stack.pop();int sum = digit + carry + adder;carry = sum / 10;sum = sum % 10;ListNode cur = new ListNode(sum);cur.next = dummy.next;dummy.next = cur;//加一次以后adder就可以置0了adder = 0;}return dummy.next;
}
3.2 链表反转实现。【持续更新】
4.链表加法
4.1 栈实现:栈顶都是两个数的最低位,所以可以一起弹出。
public ListNode addInListByStack(ListNode head1, listNode head2) {Stack<ListNode> stack1 = new Stack<>();Stack<ListNode> stack2 = new Stack<>();while (head1 != null) {stack1.push(head1);head1 = head1.next;}while (head2 != null) {stack2.push(head2);head2 = head2.next;}ListNode newHead = new ListNode(-1);int carry = 0;while (!stack1.empty() || !stack2.empty() || carry != 0) {ListNode a = new ListNode(0);ListNode b = new ListNode(0);if (!stack1.empty()) {a = stack1.pop();}if (!stack2.empty()) {b = stack2.pop();}int get_sum = a.val + b.val + carry;int ans = get_sum % 10;carry = get_sum / 10;ListNode cur = new ListNode(ans);cur.next = newHead.next;newHead.next = cur;}return newHead.next;
}
4.2 链表反转实现。
public class Solution {public ListNode addInList(ListNode head1, ListNode head2) {head1 = reverse(head1);head2 = reverse(head2);ListNode head = new ListNode(-1);ListNode cur = head;int carry = 0;while (head1 != null || head2 != null || carry != 0) {int sum = carry;if (head1 != null) {sum += head1.val;head1 = head1.next;}if (head2 != null) {sum != head2.val;head2 = head2.next;}cur.next = new ListNode(sum % 10);carry = sum / 10;cur = cur.next;}return reverse(head.next);}// 链表反转方法public ListNode reverse(ListNode head){ListNode cur = head;ListNode pre = null;while (cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}
4.3 链表减法:【持续更新】。
5.再论链表的回文序列问题
书接上回,可以使用栈或者链表反转来做。
public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}ListNode slow = head, fast = head;ListNode pre = head, prepre = null;while (fast != null && fast.next != null) {pre = slow;slow = slow.next;fast = fast.next.next;pre.next = prepre;prepre = pre;}if (fast != null) {slow = slow.next;}while (pre != null && slow != null) {if (pre.val != slow.val) {return false;}pre = pre.next;slow = slow.next;}return true;
}
如果对您有帮助,请点赞关注支持我,谢谢!❤
如有错误或者不足之处,敬请指正!❤
相关文章:
算法通关村第二关|白银|链表反转拓展【持续更新】
1.指定区间反转 1.1 头插法:将区间内遍历到的结点插入到起始处之前。 public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;// 将pre移动到区间的前一位&a…...

开发者职场“生存状态”大调研报告分析 - 第四版
听人劝、吃饱饭,奉劝各位小伙伴,不要订阅该文所属专栏。 作者:不渴望力量的哈士奇(哈哥),十余年工作经验, 跨域学习者,从事过全栈研发、产品经理等工作,现任研发部门 CTO 。荣誉:2022年度博客之星Top4、博客专家认证、全栈领域优质创作者、新星计划导师,“星荐官共赢计…...

代码与细节(一)
在用到 Java17的新特性 Unmodifiable Lists 时不知道你是否和我有同样的惊讶 为什么弄了这么多重载方法? 先说结论:为了性能。 其实一细想,都能想明白:varargs(可变参数) 的背后是数组的内存分配和初始化,相比正常的…...

AI绘画使用Stable Diffusion(SDXL)绘制中国古代神兽
一、引言 说到神奇异兽,脑海中首先就会跳出我国古代神话传说中的各种神兽。比如青龙、白虎、朱雀、玄武,再比如麒麟、凤凰、毕方、饕餮等等,这些都是大家耳熟能详的的神兽。 这些神兽不仅体现了人们丰富的创造力和想象力,更是我…...
老卫带你学---leetcode刷题(148. 排序链表)
148. 排序链表 问题: 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 示例 1:输入:head [4,2,1,3] 输出:[1,2,3,4]示例 2:输入:head [-1,5,3,4,0] 输出:[-1…...

21.1 stm32使用LTDC驱动LCD--配置说明
本文讲解如何配置LTDC驱动LCD的参数配置,以及CubeMx参数配置说明 本文使用的是淘宝买的一块带电容触摸的液晶显示屏:5寸TFT液晶显示屏高清800*480免驱40P通用RGBIPS全视角彩屏GT911 说实话,价格还是相对挺便宜的,值得入手…...

zabbix监控nginx的状态页面
zabbix监控nginx的状态页面 文章目录 zabbix监控nginx的状态页面1.环境说明2.所涉及到的知识点3.在nginx主机上安装zabbix_agent4.开启nginx状态显示页面5.进入zabbix的web页面配置主机,监控项,触发器5.1.添加主机5.2.创建监控项5.3.创建触发器 1.环境说…...

C语言初学者工具选择:vscode + MSYS2 + cmake 搭建 C环境
文章目录 前言1. MSYS2 安装1. 下载安装包2. 安装3. pacman 换清华大学源4. 安装 mingw-w64 toolchain 和 cmake ninja5. 将 toolchain 加入系统环境变量 2. 设置 vscode1. 必要的插件2. 一个简单的 vscode cmake 项目 最后C数据结构与算法CMake 前言 网上关于使用 vscode 配…...

【四:httpclient的使用】
目录 1、Demo案例2、请求一个带cookies的get请求3、请求一个带cookies的post请求案例一,案例二的properties的配置 1、Demo案例 public class MyHttpClient {Testpublic void test1() throws IOException {//用来存放我们的结果String result;HttpGet get new Htt…...
在innodb引擎中,count(*)、count(1)、count(主键)、count(字段)哪个性能最高?
在InnoDB引擎中,这四种计数值的效率高低取决于具体的数据库和数据表结构,无法一概而论哪个性能最高。不过,一般情况下可以按照以下顺序进行选择: count():统计所有行的数量。由于InnoDB引擎的行锁是锁住整行ÿ…...
华为OD 跳格子2(200分)【java】B卷
华为OD统一考试A卷B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击此链接进入:…...

javascript/python 笔记: folium feature group自动切换
1 python部分 python部分只能是静态的结果 1.1 导入库 import folium import math 1.2 数据 cell_lst表示基站位置,location_lst表示 用户实际位置(均为伪数据) cell_lst[[1.341505, 103.682498],[1.342751, 103.679604],[1.341505, 10…...
Python中的元组
Python 元组 Python 的元组与列表类似,不同之处在于元组的元素不能修改。以下是关于Python元组的一些基本信息: 元组的使用:元组是一个不可变的序列类型,使用小括号 () 来定义。元组没有增加元素append、修改元素、删除元素pop的…...

在云计算环境中,如何利用 AI 改进云计算系统和数据库系统性能
文章目录 前言一、关于唐明洁教授二、AI for System2.1 面向分布式作业的人工智能2.1.1 现阶段企业云计算系统环境所遇到的普遍痛点2.1.2 云计算系统环境所遇到的普遍痛点的解决方案(一)Google Autopilot Eurosys 2021方案(Pod级别࿰…...

OpenP2P实现内网穿透远程办公
OpenP2P是一个开源、免费、轻量级的P2P共享网络。你的设备将组成一个私有P2P网络,里面的设备可以直接访问其它成员,或者通过其它成员转发数据间接访问。如果私有网络无法完成通信,将会到公有P2P网络寻找共享节点协助通信。 相比BT网络用来共享…...

黑白棋(Othello, ACM/ICPC World Finals 1992, UVa220)rust解法
你的任务是模拟黑白棋游戏的进程。黑白棋的规则为:黑白双方轮流放棋子,每次必须让新放的棋子“夹住”至少一枚对方棋子,然后把所有被新放棋子“夹住”的对方棋子替换成己方棋子。一段连续(横、竖或者斜向)的同色棋子被…...
MySQL中如何进行表的优化和压缩?
在MySQL中,可以通过以下方式进行表的优化和压缩: 使用合适的存储引擎(Storage Engine):MySQL提供了多种存储引擎,如InnoDB、MyISAM等。不同的存储引擎在表的优化和压缩方面有不同的特点。例如,I…...
【Java】Jsoup格式化html问题(文本空格折叠等)解决方法
问题说明 Jsoup格式化html文本时,如: Document document Jsoup.parse(html);这里在对html进行格式化的时候会将如下内容: <p> aaa </p>解析成如下格式: <p> aaa </p>即空格折叠问题ÿ…...
Ansible定义各类变量,引用变量方式介绍及注册变量和vars_prompt的用法示例
目录 一.Ansible定义变量 1.用途 2.定义规则 3.变量优先级 二.命令行定义变量 三.定义主机和主机组变量 1.主机变量 (1)内置主机变量 (2)简单示例 2.主机组变量 四.定义playbook变量 1.通过vars表示定义变量ÿ…...

各类证件的版面信息收集
香港身份证的版面分析: 证件页面: 相关的版面信息: 该页面包含香港身份证的信息,可以用于版面分析; 信息来源:香港不同证件说明大汇总|回乡证|居民身份证|护照|永居_手机网易网 台湾通行证号码…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

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

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...