链表【Lecode_HOT100】

1.相交链表No.160

image-20241123212059285

image-20241123212110664

image-20241123212119015

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null||headB==null) return null;ListNode  pA=headA;ListNode  pB=headB;while(pA!=pB){pA=(pA==null)?headB:pA.next;pB=(pB==null)?headA:pB.next;}return pA; }
2.反转链表No.206

image-20241124094117014

 public ListNode reverseList(ListNode head) {ListNode curr = head;//当前节点，从头节点开始ListNode prev = null;//前一个节点，初始为nullwhile(curr!=null){ListNode nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}return prev;}
3.回文链表No.234

image-20241128094317254

  • 方法一

思路：顺序存放一个列表，倒序存放一个列表，比较两个列表是否相同。

 public boolean isPalindrome(ListNode head) {ListNode p = head;List<Integer>  list1 = new ArrayList<>();List<Integer>  list2 = new ArrayList<>();while(p!=null){list1.add(p.val);p=p.next;}//将列表倒序ListNode curr = head;ListNode prev = null;while(curr!=null){ListNode nextTemp = curr.next;curr.next = prev;prev=curr;curr=nextTemp;}while(prev!=null){list2.add(prev.val);prev=prev.next;}return list1.equals(list2);}
  • 方法二

列表+双指针

public boolean isPalindrome(ListNode head) {//使用列表+双指针List<Integer> list = new ArrayList<>();//定义链表节点ListNode curr = head;while(curr!=null){list.add(curr.val);curr=curr.next;}//定义指针int l = 0, r = list.size()-1;while(l<r){if(!list.get(l).equals(list.get(r))){return false;}l++;r--;}return true;}
4.环形链表

image-20241128094559446

  • 方法一：哈希表法
  • 思路：
    • 遍历链表，用一个哈希表记录访问过的节点。
    • 如果在遍历过程中发现当前节点已经存在于哈希表中，说明链表有环。
    • 如果遍历结束仍未发现重复节点，则链表无环。

注意： set中存放的是节点，而不是节点中的值

public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while(head!=null){if(set.contains(head)){return true;}set.add(head);head=head.next;}return false;}

  • 方法二：快慢指针法

  • 思路：

    • 使用两个指针，慢指针每次走一步，快指针每次走两步
    • 如果链表中有环，快指针会在环内追上慢指针
    • 如果快指针或其next为null，说明链表无环
public boolean hasCycle(ListNode head) {if(head==null||head.next==null){return false;}//定义快慢指针ListNode slow = head;ListNode quick = head;while(quick!=null&&quick.next!=null){slow=slow.next;quick = quick.next.next;if(slow==quick){return true;}}return false;}
5.环形链表IINo.142

image-20241129093425817

  • 方法一：哈希表法
 public ListNode detectCycle(ListNode head) {//创建HashsetHashSet<ListNode> set = new HashSet<>();while(head!=null){if(set.contains(head)){return head;}set.add(head);head = head.next;}return null;}
  • 方法二：快慢指针
public ListNode detectCycle(ListNode head) {ListNode slow = head,fast = head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){//证明有环break;}}if(fast==null||fast.next==null){return null;}//令其中一个环从头结点开始slow = head;while(slow!=fast){slow = slow.next;fast = fast.next;}return slow;}
6.合并两个有序链表No.21

image-20241129103506314

  • 方法一：列表+数组
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null&&list2==null){return null;}List<Integer> list = new ArrayList<>();//将链表放入列表list中while(list1!=null){list.add(list1.val);list1 = list1.next;}while(list2!=null){list.add(list2.val);list2 = list2.next;}Integer[] arr = list.toArray(new Integer[list.size()]);Arrays.sort(arr);//将数组转为链表ListNode head = new ListNode(arr[0]);ListNode curr =head;for(int i = 1;i<arr.length;i++){ListNode nextTem = new ListNode(arr[i]);curr.next = nextTem;curr=nextTem; }return head;}
  • 方法二：指针
 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {//创建一个新链表，首先创建一个虚拟头指针ListNode head = new ListNode(0);ListNode curr = head;//创建两个指针，分别遍历链表1、链表2;ListNode p1=list1,p2=list2;while(p1!=null&&p2!=null){if(p1.val<p2.val){curr.next = p1;p1 = p1.next;//p1指针向后移动}else{curr.next = p2;p2 = p2.next; //p2指针向后移动}curr = curr.next;//当前指针向后移动}//如果一个链表遍历完成，将另一个链表的剩余元素之间添加在后面；if(p1!=null){curr.next=p1;}else if(p2!=null){curr.next=p2;}return head.next;}
7.两数相加

image-20241201184852342

image-20241201184902728

  • 逐位相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//创建虚拟节点，从而建立新的链表ListNode head = new ListNode(0);ListNode curr= head;//记录和int sum = 0;while(l1!=null||l2!=null||sum>0){if(l1!=null){sum+=l1.val;l1=l1.next;}if(l2!=null){sum+=l2.val;l2=l2.next;}curr.next = new ListNode(sum%10);curr=curr.next;sum/=10;}return head.next;}
8.删除链表的倒数第N个结点No.19

image-20241203214224932

public ListNode removeNthFromEnd(ListNode head, int n) {//创建一个虚拟节点ListNode dummy = new ListNode(0);dummy.next = head;//定义双指针，创建快慢指针，先让快指针先走n步，当快指针走到链表末尾时，慢指针恰好到达需要删除节点的位置ListNode fast = dummy;ListNode slow = dummy;//利用for循环，让快指针先走n步for(int i = 0;i<n;i++){fast = fast.next;}//快慢指针同时走while(fast.next!=null){slow = slow.next;fast = fast.next;}//删除slow.next = slow.next.next;return dummy.next;}
9.两两交换链表中的节点No.24

image-20241203220818007

  • 方法一：迭代
public ListNode swapPairs(ListNode head) {//创建虚拟节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode curr = dummy;while(curr.next!=null&&curr.next.next!=null){ListNode first = curr.next;ListNode second = curr.next.next;//交换节点first.next = second.next;second.next = first;curr.next = second;curr = first;}return dummy.next;}
  • 方法二：递归
public ListNode swapPairs(ListNode head) {//递归if(head==null||head.next==null){return head;}//创建新的头节点ListNode newHead = head.next;head.next=swapPairs(newHead.next);newHead.next = head;return newHead;}
10.随机链表的复制No.138

image-20241204094749065

image-20241204094759109

  • 思路
    • 复制节点并插入到原链表中
    • 设置新节点的random指针
    • 拆分链表
public Node copyRandomList(Node head) {if(head==null){return null;}//1.复制节点并插入到原链表中Node curr = head;while(curr!=null){//创建新的节点Node newHead = new Node(curr.val);newHead.next = curr.next;curr.next = newHead;curr= curr.next.next; //移动到下一个原节点}//2.设置新节点的random指针curr = head;//将curr指向原来的头节点while(curr!=null){//判断random指针是否为空if(curr.random!=null){curr.next.random=curr.random.next;}curr= curr.next.next;}//3.拆分链表curr = head;Node newHead = head.next; // 新链表的头节点while(curr!=null){Node temp = curr.next;curr.next = temp.next; // 恢复原链表的 next 指针if(temp.next!=null){temp.next = temp.next.next; // 连接新链表的 next 指针}curr = curr.next; // 移动到下一个原节点}return newHead;}
11.排序链表No.148

image-20241204211509574

 public ListNode sortList(ListNode head) {// 1.如果链表中少于等于1个元素则不排序if (head == null || head.next == null) {return head;}// 2.将链表分为两部分ListNode mid = spilt(head);ListNode nextHead = mid.next;mid.next = null;// 3.递归排序链表的左右两部分ListNode l = sortList(head);ListNode r = sortList(nextHead);// 4.合并排序后的链表return merge(l, r);}// 归并排序public ListNode merge(ListNode l, ListNode r) {// 创建一个虚拟节点ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l != null && r != null) {if (l.val <= r.val) {curr.next = l;l = l.next;} else {curr.next = r;r = r.next;}curr = curr.next;}// 左半部分剩余部分if (l != null) {curr.next = l;}else{ // 右半部分剩余部分curr.next = r;}return dummy.next;}// 找到链表的中间节点public ListNode spilt(ListNode head) {// 使用快慢指针进行拆分ListNode fast = head.next;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
12.LRU缓存NO.146

image-20241205094715961

image-20241205094733111

class LRUCache {//定义双向链表class DListNode{DListNode prev;DListNode next;int key,value;public DListNode(){}public DListNode(int key,int value){this.key = key;this.value = value;}}//定义哈希表HashMap<Integer,DListNode> map = new HashMap<>();//定义缓存的长度int size = 0;//定义容量int capacity;//定义头尾节点,双向链表DListNode head,tail;public LRUCache(int capacity) {this.size=0;this.capacity=capacity;head = new DListNode();tail = new DListNode();head.next = tail;tail.prev = head;}public int get(int key) {DListNode node = map.get(key);int res = -1;//如果不存在返回-1if(node!=null){res = node.value;/*更新链表，key被访问过,放到链表的头部1.先删除2.放入头部*///删除链表节点node.prev.next = node.next;node.next.prev = node.prev;//放入头部DListNode temp = head.next;head.next = node;node.next = temp;temp.prev = node;node.prev = head;}return res;}public void put(int key, int value) {DListNode node = map.get(key);if(node!=null){node.value = value;//访问完,更新链表//删除链表节点node.prev.next = node.next;node.next.prev = node.prev;//放入头部DListNode temp = head.next;head.next = node;node.next = temp;temp.prev = node;node.prev = head;}else{DListNode newNode = new DListNode(key,value);map.put(key,newNode);//如果不存在,放入头部//放入头部DListNode temp = head.next;head.next = newNode;newNode.next = temp;temp.prev = newNode;newNode.prev = head;size++;//存入节点,个数+1;if(size > capacity){//如果个数大于容量，删除尾部节点DListNode removedNode = tail.prev;//删除节点removedNode.prev.next = removedNode.next;removedNode.next.prev = removedNode.prev;//哈希表中也删除map.remove(removedNode.key);size--;}}}
}
  • 将重复的代码抽取成方法
//手动创建一双向链表
class DListNode{DListNode prev;DListNode next;int key,val;public DListNode(){}public DListNode(int key,int val){this.key = key;this.val = val;}
}
class LRUCache {//定义双向链表，创建头尾节点DListNode head;DListNode tail;//定义个数int size = 0;//定义容量int capacity;//定义一个hashHashMap<Integer,DListNode> map = new HashMap<>();public LRUCache(int capacity) {this.size = 0;this.capacity=capacity;head = new DListNode();tail = new DListNode();head.next = tail;tail.prev = head;}public int get(int key) {DListNode node = map.get(key);int res = -1;if(node!=null){res=node.val;//因为访问过当前node，根据LRU规则，需要将此节点放入到头部，先删除，在插入removeNode(node);insertNode(node);}return res;}public void put(int key, int val) {DListNode node = map.get(key);if(node!=null){//更新valuenode.val = val;//因为访问过当前node，根据LRU规则，需要将此节点放入到头部，先删除，在插入removeNode(node);insertNode(node);}else{//创建新节点DListNode newNode = new DListNode(key,val);//放入mapmap.put(key,newNode);//插入头部insertNode(newNode);size++;if(size>capacity){//删除末尾节点DListNode removeNode = tail.prev;removeNode(removeNode);//同时删除map中元素map.remove(removeNode.key);size--;}}}public void removeNode(DListNode node){node.prev.next = node.next;node.next.prev = node.prev;}public void insertNode(DListNode node){DListNode temp = head.next;head.next = node;node.next = temp;temp.prev = node;node.prev = head;}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/34628.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

时频转换 | Matlab格拉姆角和场Gramian angular summation field一维数据转二维图像方法

时频转换 | Matlab格拉姆角和场Gramian angular summation field一维数据转二维图像方法

目录 基本介绍程序设计参考资料获取方式 基本介绍 时频转换 | Matlab格拉姆角和场Gramian angular summation field一维数据转二维图像方法 程序设计 clear clc % close all load x.mat % 导入数据 x x(1:5120); % 本数据只选择5120个点进行分析 fs 6400 ; % 数据采样频…
阅读更多...
试题转excel；pdf转excel；试卷转Excel，word试题转excel

试题转excel；pdf转excel；试卷转Excel，word试题转excel

一、问题描述 一名教师朋友&#xff0c;偶尔会需要整理一些高质量的题目到excel中 以往都是手动复制搬运&#xff0c;几百道题几乎需要一个下午的时间 关键这些事&#xff0c;枯燥无聊费眼睛&#xff0c;实在是看起来就很蠢的工作 就想着做一个工具&#xff0c;可以自动处理…
阅读更多...
借助vector实现进制转换详解

借助vector实现进制转换详解

进制转换&#xff0c;没什么可说的&#xff0c;大一级别的水平&#xff0c;不过在某些考研题目中可能会涉及到顺序栈的实现&#xff0c;本贴不使用顺序栈&#xff0c;用STL里面的vector模拟一下&#xff1a;关键在于想清楚【除留取余】的逻辑&#xff0c;至于用什么结构存放中间…
阅读更多...
快速构建NLP理论知识体系

快速构建NLP理论知识体系

NLP理论知识体系 一句话解释NLPNLP模型及原理简述1、Rag 一句话解释NLP 如果我们要实现机器翻译、情感分析、问答系统、文本摘要、聊天机器人、构造智能化的辅助文件填写模板&#xff0c;NLP可以通过现成的模型对输入的语音、文字、图片进行处理&#xff08;分词、标词性、去停…
阅读更多...
iptables防火墙（DNAT、SNAT）小实验

iptables防火墙（DNAT、SNAT）小实验

这篇是iptables服务器当中DNAT、SNAT的部分 网络拓扑图&#xff1a; 实验要求&#xff1a; 实现内外网web互访问将内web的网关指向iptables服务器ens33的IPiptables服务器添加两块网卡&#xff0c;外web服务器要跟iptables的ens36同一块网卡内部web&#xff1a;192.168.180.1…
阅读更多...
Oracle ASM特性介绍和增删盘操作

Oracle ASM特性介绍和增删盘操作

1. 介绍 1.1. 在没有ASM之前ORACLE数据库靠什么去解决存储问题&#xff1a; 裸设备:裸设备就是没有被文件系统格式化的分区或者是直接挂载到操作系统上的磁盘。ORACLE可以直接将数据写入到裸设备中&#xff0c;读写能非常优异。像ORACLE的数据文件、控制文件、REDO日志在过去…
阅读更多...
UiPath API接口说明

UiPath API接口说明

Swagger网址 私有云网址&#xff08;企业版&#xff09; https://企业/swagger/index.html 公有云网址&#xff08;社区版&#xff09; https://cloud.uipath.com/linan/LinanZhang/orchestrator_/swagger/index.html#/ 常见问题 Swagger页面测试请求时报错“You are not a…
阅读更多...
【机械加工】数字化软件打造，如何实现3D交互可视化？

【机械加工】数字化软件打造，如何实现3D交互可视化？

机械加工是制造业的重要领域之一&#xff0c;随着制造技术和工艺的不断发展&#xff0c;机械加工的精度和效率要求越来越高。HOOPS作为一款专业的3D图形引擎&#xff0c;可以为机械加工行业提供高效、灵活的3D建模、可视化和交互工具。下面将从以下几个方面介绍HOOPS技术在机械…
阅读更多...
CAMAv2: A Vision-Centric Approach for Static Map Element Annotation

CAMAv2: A Vision-Centric Approach for Static Map Element Annotation

CAMAv2: 摘要简介相关工作A. 视觉为中心的地图构建&#xff08;Vision-centric HD Map Construction&#xff09;B. 地图元素数据集&#xff08;Map Element Datasets&#xff09;1. nuScenes 数据集2. Argoverse2 数据集3. 车道线数据集 CAMAv2A. 场景重建&#xff08;Scene R…
阅读更多...
大数据新视界 -- 大数据大厂之 Hive 临时表与视图：灵活数据处理的技巧（上）（29 / 30）

大数据新视界 -- 大数据大厂之 Hive 临时表与视图：灵活数据处理的技巧（上）（29 / 30）

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…
阅读更多...
Python批量生成个性化Word录用通知书

Python批量生成个性化Word录用通知书

你是一名人力资源部门的员工&#xff0c;你需要根据一份Excel表格中的员工信息&#xff0c;为每位员工生成一份录用通知书。 Excel表格中包含了员工的姓名、性别、职位、入职日期等信息&#xff0c;你需要将这些信息填充到Word模板中&#xff0c;并生成独立的录用通知书文件。…
阅读更多...
Android显示系统（05）- OpenGL ES - Shader绘制三角形（使用glsl文件）

Android显示系统（05）- OpenGL ES - Shader绘制三角形（使用glsl文件）

一、前言&#xff1a; 上一篇文章我们使用了Shader绘制了一个基本的三角形&#xff0c;但是&#xff0c;发现那样写Shader程序特别麻烦&#xff0c;各种加双引号&#xff0c;还没有语法高亮提示。因为glsl也和java、c一样是一门语言&#xff0c;实际工程项目都是单独的glsl文件…
阅读更多...
Linux显卡驱动安装

Linux显卡驱动安装

前言 使用Windows配置环境失败&#xff0c;其中有一个包只有Linux版本&#xff0c;Windows版本的只有python3.10的&#xff0c;所以直接选用Linux来配置环境&#xff0c;显卡安装比较麻烦&#xff0c;单独出一期。 显卡驱动安装 参考文章&#xff1a;Ubuntu显卡驱动安装和这…
阅读更多...
【Linux】进程控制

【Linux】进程控制

目录 一、进程创建1.1 fork函数1.2 fork函数返回值1.3 写时拷贝1.4 fork常规用法1.5 fork调用失败的原因1.6 使用fork创建多进程 二、进程退出2.1 进程退出场景2.1.1 进程运行完毕2.1.2 代码异常终止2.1.3 小结 2.2 进程常见退出方法2.2.1 return2.2.2 调用exit函数2.2.3 调用_…
阅读更多...
smart-doc 使用

smart-doc 使用

文档地址 添加插件 <plugin><groupId>com.ly.smart-doc</groupId><artifactId>smart-doc-maven-plugin</artifactId><version>3.0.9</version><configuration><includes><!--格式为&#xff1a;groupId:artifactId;…
阅读更多...
Spring04——注解开发

Spring04——注解开发

Spring3.0启用了纯注解开发模式&#xff0c;使用Java类替代配置文件&#xff0c;开启了Spring快速开发赛道 Java类代替Spring核心配置文件&#xff0c; 配置类&#xff08;Configuration&#xff09; Configuration注解用于设定当前类为配置类ComponentScan注解用于设定扫描路…
阅读更多...
ImportError: cannot import name ‘implements‘ from ‘zope.interface‘

ImportError: cannot import name ‘implements‘ from ‘zope.interface‘

ImportError: cannot import name ‘implements’ from ‘zope.interface’ 1. 问题分析 问题原因&#xff1a; /home/user/.conda/envs/vectornet/lib/python3.8/site-packages/apex/interfaces.py中在使用zope.interace中使用了老表达。 2. 解决办法 原文件内容&#xff…
阅读更多...
多线程的操作

多线程的操作

1、Thread类 1.1 Thread类的作用 上篇博文中我们了解了线程与操作系统的关系&#xff1a;线程是操作系统中的概念&#xff0c;操作系统内核实现了线程这样的机制, 并且对用户层提供了一些 API 供用户使用&#xff0c;Java 标准库中 Thread 类可以视为是对操作系统提供的 API 进…
阅读更多...
51单片机应用开发(进阶)---串口接收字符命令

51单片机应用开发(进阶)---串口接收字符命令

实现目标 1、巩固UART知识&#xff1b; 2、掌握串口接收字符数据&#xff1b; 3、具体实现目标&#xff1a;&#xff08;1&#xff09;上位机串口助手发送多字符命令&#xff0c;单片机接收命令作相应的处理&#xff08;如&#xff1a;openled1 即打开LED1;closeled1 即关…
阅读更多...
3-5 C常用的字符串库函数

3-5 C常用的字符串库函数

1.0 字符串库函数 strlen()函数用于返回字符串的长度&#xff0c;不包括结尾\0 uint32_t strlen(char *str) {uint32_t len 0;while (str[len] ! \0){len;}return len; } 编译器在处理字符串时&#xff0c;会自动的在数据末尾添加ASCI码“0对应十进制0&#xff0c;便于程序对…
阅读更多...
最新文章

Copyright @ 2022~2023