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

【算法】链表题型总结

 链表题型可分为快慢指针虚拟头节点两种解题技巧。

快慢指针

使用两个指针(快指针和慢指针),以不同的速度遍历链表,解决与链表位置、环检测相关的问题。

反转链表

  • 快慢指针,慢指针一次走一步,快指针一次走两步,直到快指针为null,返回慢指针节点

public ListNode middleNode(ListNode head){ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}

判断回文链表

  • 找到链表中间节点 + 反转后段链表,然后比较前后两段链表是否相等

环形链表

  • 判断是否有环:快慢指针,慢指针一次走一步,快指针一次走两步,如果相遇说明有环

public boolean hasCycle(ListNode head) {ListNode last = head;ListNode fast = head;while (fast != null && fast.next != null){if (fast == last){return true;}fast = fast.next.next;last = last.next;}return false;}
  • 找到环的首个节点:first指针指向头节点,second指针指向当前快指针,两个指针同时遍历到相遇

if (last == fast){ListNode first = head;ListNode second = fast;while (first != second){first = first.next;second = second.next;}return first;
}

删除链表倒数第N个节点

  • 快慢指针,快指针先走n个节点,然后快慢指针同时移动,当快指针为null,删除慢指针。

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dumy = new ListNode(0);dumy.next = head;ListNode last = dumy;ListNode fast = head;for (int i = 0; i < n; i ++){fast = fast.next;}while (fast != null){fast = fast.next;last = last.next;}last.next = last.next.next;return dumy.next;}

虚拟头节点

在链表头部添加一个虚拟节点(dummy node),简化边界条件处理,尤其是涉及头节点操作的问题。

合并两个升序链表

  • 创造虚拟头节点,然后比较两个链表,依次向后添加

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dump = new ListNode(0);ListNode cur = dump;while (list1 != null && list2 != null){if (list1.val < list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null){cur.next = list1;}if (list2 != null){cur.next = list2;}return dump.next;}

链表相加

  • 创造虚拟头节点,依次相加两链表节点,sum = x + y + carry,carry = sum/10,sum = sum % 10

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dump = new ListNode(0);ListNode cur = dump;int carry = 0;while (l1 != null || l2 != null){int x = 0, y = 0;if (l1 != null){x = l1.val;}if (l2 != null){y = l2.val;}int sum = x + y + carry;carry = sum / 10;sum = sum % 10;cur.next = new ListNode(sum);cur = cur.next;if (l1 != null){l1 = l1.next;}if (l2 != null){l2 = l2.next;}}if (carry == 1){cur.next = new ListNode(carry);}return dump.next;}

两两交换链表中的节点

  • 创造虚拟头节点,创建one节点指向虚拟头节点,two节点 = one.next,three节点 = one.next.next,temp提前存one.next.next.next,然后one.next = three,three.next = two,two.next = temp

public ListNode swapPairs(ListNode head) {ListNode dumy = new ListNode(0);dumy.next = head;ListNode one = dumy;ListNode two;ListNode three;while (one.next != null && one.next.next != null){ListNode temp = one.next.next.next;two = one.next;three = one.next.next;one.next = three;three.next = two;two.next = temp;one = two;}return dumy.next;}

排序链表

  • 归并排序,把当前链表一分为二(找到链表中间节点),再对左右子链表递归排序(合并两个升序链表)

public ListNode sortList(ListNode head) {if (head == null || head.next == null){return head;}ListNode mid = findMiddle(head);ListNode rightHead = mid.next;mid.next = null;ListNode left = sortList(head);ListNode right = sortList(rightHead);return mergeTwoLists(left, right);}private ListNode findMiddle(ListNode head){ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next;}return slow;}private ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null && l2 != null){if (l1.val < l2.val){curr.next = l1;l1 = l1.next;}else {curr.next = l2;l2 = l2.next;}curr = curr.next;}if (l1 != null){curr.next = l1;}if (l2 != null){curr.next = l2;}return dummy.next;}

其他 

相交链表

  • 两个指针,先遍历出两个链表的长度,然后长链表和短链表同一长度(长链表指针先遍历长度差的节点),最后比较两段链表是否相等

相关文章:

【算法】链表题型总结

链表题型可分为快慢指针和虚拟头节点两种解题技巧。 快慢指针 使用两个指针&#xff08;快指针和慢指针&#xff09;&#xff0c;以不同的速度遍历链表&#xff0c;解决与链表位置、环检测相关的问题。 反转链表 快慢指针&#xff0c;慢指针一次走一步&#xff0c;快指针一次…...

【C++】对字符串的常用操作

C 中的字符串操作主要通过两种方式实现&#xff1a;使用 C 风格的字符串&#xff08;字符数组&#xff09;和使用 C 标准库中的 std::string 类型。大多数现代 C 程序使用 std::string 进行字符串处理&#xff0c;因为它提供了许多便捷的成员函数来处理字符串操作。以下是常见的…...

人工智能AI在汽车设计领域的应用探索

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…...

Linux mkdir 命令

Linux mkdir&#xff08;英文全拼&#xff1a;make directory&#xff09;命令用于创建目录。 语法 mkdir [-p] dirName 参数说明&#xff1a; -p 确保目录名称存在&#xff0c;不存在的就建一个。 实例 在工作目录下&#xff0c;建立一个名为 runoob 的子目录 : mkdir …...

gin框架学习笔记

初始gin package mainimport "github.com/gin-gonic/gin"type Response struct {Code int json:"code"Msg string json:"msg"Data any json:"data" }func index(c *gin.Context) {c.JSON(200, Response{Code: 0,Msg: "1…...

什么是预训练语言模型下游任务?

问题&#xff1a;Word2Vec模型是预训练模型吗&#xff1f; 由于训练的特性&#xff0c;word2Vec模型一定是与训练模型。给定一个词先使用独热编码然后使用预训练好的Q矩阵得到这个词的词向量。这里指的是词向量本身就是预训练的语言模型。 什么是下游任务&#xff1f; 在自然…...

cursor 弹出在签出前,请清理仓库工作树 窗口

问题出现的背景&#xff1a;是因为我有两台电脑开发&#xff0c;提交后&#xff0c;另一个电脑的代码是旧的&#xff0c;这个时候我想拉取最新的代码&#xff0c;就会出现如下弹窗&#xff0c;因为这个代码暂存区有记录或者工作区有代码的修改&#xff0c;所以有冲突&#xff0…...

Ubuntu2204下使用NVIDIA GeForce RTX 4090进行DeepSeek-R1-Distill-Llama-8B模型微调

Ubuntu2204下使用NVIDIA GeForce RTX 4090进行DeepSeek-R1-Distill-Llama-8B模型微调 环境准备创建Python微调环境准备数据集准备模型文件 模型微调模型预测原始模型预测微调模型预测 使用unsloth&#xff0c;可以方便地对大模型进行微调。以微调DeepSeek-R1-Distill-Llama-8B为…...

Ubuntu20.04安装Redis

目录 切换到root用户 使用 apt install redis 安装redis 修改配置文件 ​编辑 重新启动服务器 使用Redis客户端连接服务器 切换到root用户 如果没有切换到root用户的&#xff0c;切换到root用户。 使用 apt install redis 安装redis 遇到y/n直接y即可。 redis安装好之…...

【Word2Vec】Skip-gram 的直观理解(深入浅出)

01 什么是skip-gram 一句话来说就是&#xff0c;给定中心词&#xff0c;然后预测其周围的词&#xff1a; 02 模型结构 对于skip-gram来说&#xff0c;输入是一个[1 x V]维的ont-hot向量&#xff0c;其中V为词表大小&#xff0c;值为1的那一项就表示我们的中心词。经过一个[V x…...

MQ 笔记

什么是消息队列&#xff1f; 消息队列&#xff08;Message Queue, MQ&#xff09;是一种用于在分布式系统中传递消息的中间件技术。 它允许应用程序通过发送和接收消息进行异步通信。 消息队列的核心思想是解耦生产者和消费者&#xff0c;生产者将消息发送到队列中&#xff…...

leetcode第216题组合总和Ⅲ

原题出于leetcode第216题https://leetcode.cn/problems/combination-sum-iii/description/题目为&#xff1a; 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表…...

【零基础C语言】第四节 数组

【零基础C语言系列】 【零基础C语言】第一节 C语言概述【数制进制码制】-CSDN博客 【零基础C语言】第二节 数据类型、运算符、表达式-CSDN博客 【零基础C语言】第三节 控制结构-CSDN博客 一、一维数组...

20250225-代码笔记03-class CVRPModel AND other class

文章目录 前言一、class CVRPModel(nn.Module):__init__(self, **model_params)函数功能函数代码 二、class CVRPModel(nn.Module):pre_forward(self, reset_state)函数功能函数代码 三、class CVRPModel(nn.Module):forward(self, state)函数功能函数代码 四、def _get_encodi…...

京准电钟快讯:NTP时钟同步服务在智造行业应用

京准电钟快讯&#xff1a;NTP时钟同步服务在智造行业应用 京准电钟快讯&#xff1a;NTP时钟同步服务在智造行业应用 一、NTP技术概述 基本原理 NTP&#xff08;Network Time Protocol&#xff09;是一种用于同步计算机系统时间的网络协议&#xff0c;通过分层时钟源&#xff…...

【Qt】详细介绍如何在Visual Studio Code中编译、运行Qt项目

Visual Studio Code一只用的顺手&#xff0c;写Qt的时候也能用VS Code开发就方便多了。 理论上也不算困难&#xff0c;毕竟Qt项目其实就是CMake&#xff08;QMake的情况这里就暂不考虑了&#xff09;项目&#xff0c;VS Code在编译、运行CMake项目还是比较成熟的。 这里笔者打…...

jsherp importItemExcel接口存在SQL注入

一、漏洞简介 很多人说管伊佳ERP&#xff08;原名&#xff1a;华夏ERP&#xff0c;英文名&#xff1a;jshERP&#xff09;是目前人气领先的国产ERP系统虽然目前只有进销存财务生产的功能&#xff0c;但后面将会推出ERP的全部功能&#xff0c;有兴趣请帮点一下 二、漏洞影响 …...

Node.js, Bun, Deno 比较概述

以下是 Node.js、Bun 和 Deno 的对比分析 概览 对比维度Node.jsDenoBun首次发布200920202022创始人Ryan DahlRyan Dahl&#xff08;Node.js 原作者&#xff09;Jarred Sumner运行时引擎V8&#xff08;Chrome&#xff09;V8&#xff08;Chrome&#xff09;JavaScriptCore&#…...

大白话跨域问题怎么破,解决方法有啥?

大白话跨域问题怎么破&#xff0c;解决方法有啥&#xff1f; 啥是跨域问题 咱先说说啥是跨域。你可以把每个网站想象成一个独立的小房子&#xff0c;每个房子都有自己的地址&#xff08;也就是域名&#xff09;。正常情况下&#xff0c;一个房子里的东西只能在这个房子里用&a…...

DeepSeek R1满血+火山引擎详细教程

DeepSeek R1满血火山引擎详细教程 一、安装Cherry Studio。 Cherry Studio AI 是一款强大的多模型 AI 助手,支持 iOS、macOS 和 Windows 平台。可以快速切换多个先进的 LLM 模型,提升工作学习效率。下载地址 https://cherry-ai.com/ 认准官网&#xff0c;无强制注册。 这…...

Pytorch中的ebmedding到底怎么理解?

在 PyTorch 中&#xff0c;nn.Embedding 是一个用于处理离散符号映射到连续向量空间的模块。它通常用于自然语言处理&#xff08;NLP&#xff09;任务&#xff08;如词嵌入&#xff09;、处理分类特征&#xff0c;或任何需要将离散索引转换为密集向量的场景。 核心理解 功能&am…...

【JAVA面试题】什么是面向对象?谈谈你对面向对象的理解。

【JAVA面试题】什么是面向对象&#xff1f;谈谈你对面向对象的理解 在 Java 面试中&#xff0c;面向对象 是一个高频考点。它不仅是一种编程思想&#xff0c;更是现代软件开发的核心方法论。本文将从 面向对象的概念、与面向过程的对比、以及 面向对象的三大特性&#xff08;封…...

【C】链式二叉树算法题1 -- 单值二叉树

leetcode链接https://leetcode.cn/problems/univalued-binary-tree/description/ 1 题目描述 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时&#xff0c;才返回 true&#xff1b;否则返回 false。 示例 1&#xff1…...

基于单片机的GPS定位系统设计

1 系统硬件 1.1单片机模块 单片机的种类和型号可以说是有成百上千种&#xff0c;很多大的公司和企业都生产开发自己的单片机芯片&#xff0c;并且广泛应用于各种产品。Intel、 philips、 摩托罗拉、凌阳、宏晶等等种类繁多。大体上可以分为51系列单片机和非51系列单片机。 其…...

[React]Render Props、自定义Hooks和Context API优化详解

关于React中的Render Props、自定义Hooks和Context API优化的详解。我需要根据我搜索到的资料来综合回答这三个部分。首先&#xff0c;我需要分别理解每个概念的定义、用途以及优化方法。 首先看Render Props。根据Render Props是一种通过传递函数作为prop来共享组件间逻辑的技…...

关于大型语言模型的结构修剪

本文介绍了一种名为 **LLM-Pruner** 的方法&#xff0c;用于对大型语言模型&#xff08;LLMs&#xff09;进行结构化剪枝&#xff0c;以减少模型大小和计算需求&#xff0c;同时保留其多任务解决和语言生成能力。LLM-Pruner 通过依赖检测和重要性估计实现高效剪枝&#xff0c;并…...

【语法】C++中string类中的两个问题及解答

贴主在学习string类时遇到过两个困扰我的问题&#xff0c;今天拿出来给大家分享一下我是如何解决的 一、扩容时capacity的增长问题 在string的capacity()接口中&#xff0c;调用的是这个string对象的容量(可以存多少个有效字符)&#xff0c;而size()是调用的string对象现在有…...

Linux(centOS) 命令提示符格式修改(PS1)

1. 命令提示符的组成 命令提示符&#xff08;PS1&#xff09;通常由以下部分组成&#xff1a; 部分示例说明[ 和 ][...]提示符的开头和结尾&#xff0c;用于视觉分隔。用户名root 或 tianjiajie当前登录的用户。root 是超级用户&#xff0c;普通用户可能是其他名称。分隔用户…...

QwenVL 2.5-本地安装编译布署全教程

开篇 DeepSeek开源后我国又开源了一个震撼大模型,QwenVL2.5,这是一个多模态的模形,它可以认图、识图、更能作图,还能读懂video。 Qwen2.5-VL 的主要特点如下所示: 感知更丰富的世界:Qwen2.5-VL 不仅擅长识别常见物体,如花、鸟、鱼和昆虫,还能够分析图像中的文本、图表…...

Hutool - JWT:轻松玩转 JSON Web Token

各位开发者朋友们&#xff0c;在现代的前后端分离开发模式里&#xff0c;身份验证和授权可是至关重要的环节。JSON Web Token&#xff08;JWT&#xff09;作为一种轻量级的身份验证和授权机制&#xff0c;在很多项目中都得到了广泛应用。它可以在客户端和服务器之间安全地传输信…...

2024年第十五届蓝桥杯大赛软件赛省赛Python大学A组真题解析《更新中》

文章目录 试题A: 拼正方形(本题总分:5 分)解析答案试题B: 召唤数学精灵(本题总分:5 分)解析答案试题C: 数字诗意解析答案试题D:回文数组试题A: 拼正方形(本题总分:5 分) 【问题描述】 小蓝正在玩拼图游戏,他有7385137888721 个2 2 的方块和10470245 个1 1 的方块,他需…...

【2025年2月28日稳定版】小米路由器4C刷机Immortalwrt 23.05.4系统搭载mentohust 0.3.1插件全记录

小米路由器4C刷机Immortalwrt系统搭载mentohust插件全记录 首先将路由器按住后面的reset&#xff0c;用一个针插进去然后等待5s左右&#xff0c;松开&#xff0c;即可重置路由器。 然后要用物理网线物理连接路由器Lan口和电脑&#xff0c;并将路由器WAN口连接至网口。确保电脑…...

W3C标准和ES规范之一文通

W3C标准和ES规范之一文通 以下是关于W3C标准和ES规范的透彻解析&#xff0c;通过结构化对比和生活化类比帮助理解和记忆&#xff1a; 一、核心概念对比&#xff08;总览&#xff09; 维度W3C标准ES规范&#xff08;ECMAScript&#xff09;定位Web技术的建筑蓝图JavaScript的语…...

Linux:应用层协议

协议是一种 "约定". socket api的接口, 在读写数据时, 都是按 "字符串" 的方式来发送接收的. 如果我们要传输一些"结构化的数据" 怎么办呢? 无论我们采用什么方案, 只要保证, 一端发送时构造的数据, 在另一端能够正确的进行解析, 就是ok的. 这种…...

深度学习五大模型:CNN、Transformer、BERT、RNN、GAN详细解析

# 深度学习五虎将&#xff1a;当CNN遇见Transformer的奇幻漂流 ## 序章&#xff1a;AI江湖的兵器谱排行 2012年&#xff0c;多伦多大学的厨房里&#xff0c;Hinton的学生们用GPU煎了个"AlexNet"荷包蛋&#xff0c;从此开启了深度学习的热兵器时代。如今五大模型各显…...

微服务组件详解——sentinel

1.启动sentinel&#xff1a; 下载jar sentinel-dashboard-1.8.0.jar 使用以下命令直接运行 jar 包&#xff08;JDK 版本必须≥ 1.8&#xff09;&#xff1a; java -Dserver.port9999 -jar D:\sentinel-dashboard-1.8.0.jar 控制台访问地址&#xff1a;http://localhost:9999…...

波导阵列天线 学习笔记11双极化全金属垂直公共馈电平板波导槽阵列天线

摘要&#xff1a; 本communicaition提出了一种双极化全金属垂直公共馈电平板波导槽阵列天线。最初提出了一种公共馈电的单层槽平板波导来实现双极化阵列。此设计消除了传统背腔公共馈电的复杂腔体边缘的必要性&#xff0c;提供了一种更简单的天线结构。在2x2子阵列种发展了宽十…...

swift 开发效率提升工具

安装github copliot for xcode github/CopilotForXcode brew install --cask github-copilot-for-xcode安装swiftformat for xcode brew install swiftformatXcode Swift File代码格式化-SwiftFormat...

3-5 WPS JS宏 工作表的移动与复制学习笔记

************************************************************************************************************** 点击进入 -我要自学网-国内领先的专业视频教程学习网站 *******************************************************************************************…...

Centos7部署k8s(单master节点安装)

单master节点部署k8s集群(Centos) 一、安装前准备 1、修改主机名 按照资源准备修改即可 # master01 hostnamectl set-hostname master01 ; bash # node1 hostnamectl set-hostname node1 ; bash # node2 hostnamectl set-hostname node2 ; bash2、修改hosts文件 以下命令所…...

Tomcat

1.Tomcat是什么&#xff1f; Tomcat 是一个开源的、轻量级的 Servlet 容器&#xff0c;也被称为 Web 服务器&#xff0c;由 Apache 软件基金会的 Jakarta 项目开发&#xff0c;在 Java Web 开发领域应用广泛。 1&#xff09;Servlet 容器&#xff1a;Servlet 是 Java 语言编写…...

基于SpringBoot+Vue的电影订票及评论网站的设计与实现(源码+SQL脚本+LW+部署讲解等)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

地基简识Spring MVC 组件

Spring MVC 是一个基于 MVC 设计模式的框架&#xff0c;其核心组件协同工作以处理 HTTP 请求并生成响应。以下是各组件的详细说明及其协作流程&#xff1a; 一、​核心组件 ​DispatcherServlet&#xff08;前端控制器&#xff09;​ ​作用&#xff1a;接收所有请求并协调其他…...

如何通过Python网络爬虫技术应对复杂的反爬机制?

要使用Python网络爬虫技术绕过复杂的反爬虫机制&#xff0c;可以采取以下几种策略&#xff1a; 设置User-Agent&#xff1a;通过设置不同的User-Agent&#xff0c;模拟正常用户的浏览器访问&#xff0c;避免被网站识别为爬虫。可以使用fake_useragent库来随机生成User-Agent。…...

深入浅出:Spring AI 集成 DeepSeek 构建智能应用

Spring AI 作为 Java 生态中备受瞩目的 AI 应用开发框架&#xff0c;凭借其简洁的 API 设计和强大的功能&#xff0c;为开发者提供了构建智能应用的强大工具。与此同时&#xff0c;DeepSeek 作为领先的 AI 模型服务提供商&#xff0c;在自然语言处理、计算机视觉等领域展现了卓…...

Node.js二:第一个Node.js应用

精心整理了最新的面试资料和简历模板&#xff0c;有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 创建的时候我们需要用到VS code编写代码 我们先了解下 Node.js 应用是由哪几部分组成的&#xff1a; 1.引入 required 模块&#xff1a;我们可以使用 requi…...

【HarmonyOS Next】鸿蒙状态管理装饰器V1和V2混用方案

【HarmonyOS Next】鸿蒙状态管理装饰器V1和V2混用方案 一、V1和V2为什么需要混用 自从api7开始&#xff0c;一直到api10。V1的实际使用中&#xff0c;开发人员发现Observed和ObjectLink 监听实现多层级嵌套对象的更新的方案&#xff0c;太过于臃肿。当需要监听处理更新的多层…...

【技海登峰】Kafka漫谈系列(三)详解Kafka的数据结构与存储机制

【技海登峰】Kafka漫谈系列(三)详解Kafka的数据结构与存储机制 Kafka 使用消息日志(Log)机制来持久化保存数据,我们知道Kafka实际是以Partition分区为单位进行负载均衡和资源分配,每个Partition又由多个Replica副本组成,副本之间分布于不同的Broker上来保证高可用,因此…...

PyCharm接入本地部署DeepSeek 实现AI编程!【支持windows与linux】

今天尝试在pycharm上接入了本地部署的deepseek&#xff0c;实现了AI编程&#xff0c;体验还是很棒的。下面详细叙述整个安装过程。 本次搭建的框架组合是 DeepSeek-r1:1.5b/7b Pycharm专业版或者社区版 Proxy AI&#xff08;CodeGPT&#xff09; 首先了解不同版本的deepsee…...

腾讯云扩容记录

腾讯云扩容&#xff1a; sudo yum install -y cloud-utils-growpart 安装扩容工具 sudo file -s /dev/vda1 有数据 sudo LC_ALLen_US.UTF-8 growpart /dev/vda 1 sudo resize2fs /dev/vda1 df -Th 完毕 以下是对执行的命令的详细解释以及背后的原理&#xff1a; 1. 安装 cloud…...