链表 OJ（一）

移除链表元素

题目连接：
https://leetcode.cn/problems/remove-linked-list-elements/description/

在这里插入图片描述

使用双指针法，开始时，一个指针指向头节点，另一个指针指向头节点的下一个结点，然后开始遍历链表删除结点。

这里要注意如果是空链表的话，使用双指针第二个指针会发生空指针异常，所以要判断一下

最后程序运行到最后，我们还差头节点没有判断，最后加上即可。

class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null) {return head;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == val) {prev.next = cur.next;} else {prev = cur;}cur = cur.next;}if(head.val == val) {head = head.next;}return head;}
}

反转链表

题目连接：
https://leetcode.cn/problems/reverse-linked-list/description/

在这里插入图片描述

我们还是使用双指针，不过这次有一个指针就是头指针，因为反转链表之后的头指针会发生改变，那还不如直接让头指针一起移动，先将另一个指针指向头指针的下一个结点，然后开始遍历链表，把每一个结点的指针指向的对象变为前面的对象。

class Solution {public ListNode reverseList(ListNode head) {if(head == null) {return head;}ListNode cur = head.next;head.next = null;while(cur != null) {ListNode tmp = cur.next;cur.next = head;head = cur;cur = tmp;}return head;}
}

链表的中间结点

题目链接：
https://leetcode.cn/problems/middle-of-the-linked-list/description/

在这里插入图片描述

使用快慢指针，快指针每次走两步，慢指针每次走一步，最后慢指针所指向的结点就是 中间结点

原理：fast = 2slow = 总路程

这里要注意循环的结束条件：
在这里插入图片描述当fast== null 并且 fast.next == null时，才能进入循环，并且 fast==null,要放在前面，因为只用fast不是null时才能进行 fast.next 的判断

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

返回倒数第 k 个节点

题目链接：
https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/

在这里插入图片描述

还是使用快慢指针，先让快指针走 k-1 步，然后慢指针和快指针一起走，每次走一步，最后快指针走到最后一个结点时，慢指针所指向的节点就是倒数第 k 个节点。

原理就是让slow和fast的差值j就是k

class Solution {public int kthToLast(ListNode head, int k) {ListNode fast = head;ListNode slow = head;for(int i=0; i<k-1; i++) {fast = fast.next;}while(fast.next != null) {slow = slow.next;fast = fast.next;}return slow.val;}
}

合并两个有序的链表

题目链接：
https://leetcode.cn/problems/merge-two-sorted-lists/description/
在这里插入图片描述

创建一个新的头节点，list1和list2开始遍历各自的链表，然后比较，插入到新链表中，最后再看一下哪些链表没有遍历完，然后把没有遍历完的链表直接插入即可。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null) {return list2;}if(list2 == null) {return list1;}ListNode newHead = new ListNode();ListNode cur = newHead;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 newHead.next;}
}

分割链表

题目链接：
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

在这里插入图片描述

我们可以将单链表拆成两个链表，一个链表存储小于x 的结点，另一个链表存储大于等于x 的结点，然后将两个链表合并

这里建议使用带头链表，也就是我们常说的带哨兵位的链表，这个链表最大的好处就是可以避免头插的复杂情况，既然使用了哨兵位，就要知道最后哨兵位是要被丢弃的。

public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode headA = new ListNode(-1);ListNode aLast = headA;ListNode headB =  new ListNode(-1);ListNode bLast = headB;ListNode cur = pHead;while(cur != null) {if(cur.val < x) {aLast.next = cur;aLast = aLast.next;} else {bLast.next = cur;bLast = bLast.next;}cur = cur.next;}aLast.next = headB.next;bLast.next = null;return headA.next;}
}

链表的回文结构

题目链接：
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
在这里插入图片描述

解题思路：
我们可以使用快慢指针来遍历链表找到中间结点，然后就可以把后半部分的链表进行反转，之后从这个链表头尾结点开始向中间遍历。

易错点：
1.链表的结点个数有奇数和偶数两种类型，我们需要分别讨论
2.区分奇数个结点还是偶数个结点可以从一开始找完中间结点的时候，从fast入手,因为找中间结点的循环结束就是fast最后指向尾节点还是null。
3.要一定要保存好fast的信息，因为后面在反转链表的时候fast其实已经发生了改变。

public class PalindromeList {public boolean chkPalindrome(ListNode A) {//如果是空链表返回trueif(A == null) {return true;}ListNode slow = A;ListNode fast = A;//找到中间结点while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//保存fast的结点信息，避免后面反转链表丢失信息boolean isOdd = true;//是否是奇数个结点if(fast == null) {isOdd = false;}//反转后半部分的链表ListNode prev = slow;ListNode cur = slow.next;while(cur != null) {ListNode curN = cur.next;cur.next = prev;prev = cur;cur = curN;}//前后遍历链表ListNode pA = A;ListNode last = prev;//偶数个结点if(!isOdd) {while(pA.next != last) {if(pA.val != last.val) {return false;}pA = pA.next;last = last.next;}if(pA.val != last.val) {return false;}}if (isOdd) { //奇数个结点while(pA != last) {if(pA.val != last.val) {return false;}pA = pA.next;last = last.next;}}return true;}
}

相交链表

题目链接：
https://leetcode.cn/problems/intersection-of-two-linked-lists/

在这里插入图片描述

由于是相交链表，在公共结点之前两个链表可能有一个差值，如果我们能找到这个差值，让长的链表先走差值不属，然后两个链表一起遍历，直到相遇到公共结点。

这个差值就是两个链表的长度的差。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = 0;int lenB = 0;ListNode cur = headA;while(cur != null) {lenA++;cur = cur.next;}cur = headB;while(cur != null) {lenB++;cur = cur.next;}int k = 0;ListNode pl = null;ListNode ps = null;if(lenA > lenB) {k = lenA - lenB;pl = headA;ps = headB;} else {k = lenB - lenA;pl = headB;ps = headA;}while(k != 0) {pl = pl.next;k--;}while(pl != ps) {pl = pl.next;ps = ps.next;}return pl;}
}

环形链表

题目链接：
https://leetcode.cn/problems/linked-list-cycle/

在这里插入图片描述

这里使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针运动到fast == null 或者 fast .next == null 这个条件时，说明链表不存在环，如果有链表存在环，那么快指针就会先进入到环中一直做圆周运动，一定会存在某一个时刻快慢指针会相遇，这时候返回true即可。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}} return false;}
}

为什么快指针每次走两步，慢指针走一步可以？

快指针会率先进入环中，然后慢指针后晚一点进入环中，由于两个指针的速度是每次差一步，也就是说两个指针每运动一次，二者之间的距离就会缩短1步，最后两个指针一定会相遇。

快指针一次走3步，走4步，…n步行吗？
快指针如果每次走三步，假设两个指针的位置如下：
在这里插入图片描述
那二者永远都不会相遇

其他情况由读者自行探讨~~

环形链表Ⅱ （找入口点）

题目链接：
https://leetcode.cn/problems/linked-list-cycle-ii/description/

在这里插入图片描述

我们还是使用快慢指针来做。

假设起点与入口点的距离为 x ，环的周长为 C ，慢指针与快指针相遇点离起点的距离为L ：
在这里插入图片描述
慢指针所走的路程为 x + L
快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)

这里解释一下两者的路程计算问题：
在慢指针还没有进入口点的时候，就已经至少路过一次相遇点，所以当慢指针刚刚进入环中的时候，快指针最少已经走了一圈，最多走了 n 圈。
因为慢指针刚进入环中的时候，快指针和它最多相差一个圈的距离，并且快指针的速度比慢指针的速度要快，所以慢指针是不可能走完一圈的（假设慢指针走完一圈，那快指针一定走完一圈再多一点，所以慢指针在完成一圈之前一定会被追上），所以慢指针所走的路程为 x + L，快指针所走的路程为 x + L + nC (n为正整数，n = 1,2,3,4…)中的 nC 是遇到慢指针之前就已经完成好的

当快慢指针在环中相遇时，由于快指针的速度是慢指针的速度的两倍，所以慢指针的路程是快指针的一半，即 2 * (x + L) = x + L + nC，化简整理得 x + L = nC 即 x = nC - L

推导结论：
让一个指针从头开始遍历，另一个指针从相遇点开始遍历，两个指针每次走一步，一定会在入口点相遇。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(slow == fast) {break;}}//没有环if(fast == null || fast.next == null) {return null;}ListNode meet = fast;ListNode str = head;while(meet != str) {meet = meet.next;str = str.next;}return str;}
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【SGX系列教程】（五）enclave多线程测试，以及EPC内存测试

【SGX系列教程】（五）enclave多线程测试，以及EPC内存测试

文章目录 一. 概述二. 原理分析2.1 多线程在Enclave中的实现流程2.2 多线程和EPC内存分配之间的冲突2.3 解决多线程和EPC内存分配冲突的策略 三. 源码分析3.1 代码结构3.2 源码3.2.1 App文件夹3.2.2 Enclave文件夹3.2.3 Makefile 3.3 总结 四.感谢支持 一. 概述 在Intel SGX环境…
阅读更多...
HarmonyOS(43) @BuilderParam标签使用指南

HarmonyOS(43) @BuilderParam标签使用指南

BuilderParam BuilderParam使用举例定义模板定义具体实现BuilderParam初始化 demo源码参考资料 BuilderParam 该标签有的作用有点类似于设计模式中的模板模式&#xff0c;类似于指定一个UI占位符&#xff0c;具体的实现交给具体的Builder&#xff0c;顾名思义&#xff0c;可以…
阅读更多...
【算法】排序算法介绍 附带C#和Python实现代码

【算法】排序算法介绍 附带C#和Python实现代码

1. 冒泡排序（Bubble Sort） 2. 选择排序（Selection Sort） 3. 插入排序（Insertion Sort） 4. 归并排序（Merge Sort） 5. 快速排序（Quick Sort） 排序算法是计算机科学中的一个基础而重要的部分，用于将一组数据按照一定的顺序排列。下面介绍几种常见的排序算法，…
阅读更多...
可控学习综述：信息检索中的方法、应用和挑战

可控学习综述：信息检索中的方法、应用和挑战

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
YOLOv10改进 | Conv篇 | 利用YOLO-MS的MSBlock轻量化网络结构（既轻量又长点）

YOLOv10改进 | Conv篇 | 利用YOLO-MS的MSBlock轻量化网络结构（既轻量又长点）

一、本文介绍 本文给大家带来的改进机制是利用YOLO-MS提出的一种针对于实时目标检测的MSBlock模块(其其实不能算是Conv但是其应该是一整个模块)&#xff0c;我们将其用于C2f中组合出一种新的结构&#xff0c;来替换我们网络中的模块可以达到一种轻量化的作用&#xff0c;我将其…
阅读更多...
【Python基础】代码如何打包成exe可执行文件

【Python基础】代码如何打包成exe可执行文件

本文收录于 《一起学Python趣味编程》专栏&#xff0c;从零基础开始&#xff0c;分享一些Python编程知识&#xff0c;欢迎关注&#xff0c;谢谢&#xff01; 文章目录 一、前言二、安装PyInstaller三、使用PyInstaller打包四、验证打包是否成功五、总结 一、前言 本文介绍如何…
阅读更多...
SFUZZ模糊测试平台全新升级，从标准到实践助力车企安全出海

SFUZZ模糊测试平台全新升级，从标准到实践助力车企安全出海

开源网安模糊测试平台SFuzz全新升级&#xff0c;参照各国相关标准要求进行针对性建设&#xff0c;可为智能网联汽车信息安全测试提供更为强大的工具支持。SFuzz向被测系统输入大量随机数据&#xff0c;模拟各种异常情况&#xff0c;可以发现被测系统内潜在的缺陷和漏洞&#xf…
阅读更多...
ChatGPT提问获取高质量答案的艺术PDF下载书籍推荐分享

ChatGPT提问获取高质量答案的艺术PDF下载书籍推荐分享

ChatGPT高质量prompt技巧分享pdf&#xff0c; ChatGPT提问获取高质量答案的艺术pdf。本书是一本全面的指南&#xff0c;介绍了各种 Prompt 技术的理解和利用&#xff0c;用于从 ChatGPTmiki sharing中生成高质量的答案。我们将探讨如何使用不同的 Prompt 工程技术来实现不同的目…
阅读更多...
C语言——结构体

C语言——结构体

一、定义和使用结构体 1.1概述 前面我们见过的数据类型&#xff0c;比如int,float,char等是在程序中简单的使用&#xff0c;如果我们要根据自己的需求来建立一些复杂的数据&#xff0c;就需要用到结构体。 例如&#xff0c;一个学生的学号&#xff0c;姓名&#xff0c;性别&am…
阅读更多...
Python 利用pandas处理CSV文件（DataFrame的基础用法）

Python 利用pandas处理CSV文件（DataFrame的基础用法）

前面介绍过通过Python标准库中的CSV模块处理CSV文件&#xff1a; Python 利用CSV模块处理数据 相比CSV模块&#xff0c;pandas的功能更加强大&#xff0c;本文将简单介绍如何通过pandas来处理CSV文件。 文章目录 一、pandas简介二、用法示例2.1 读取CSV文件2.1.1 read_csv参数…
阅读更多...
Python 视频的色彩转换

Python 视频的色彩转换

这篇教学会介绍使用OpenCV 的cvtcolor() 方法&#xff0c;将视频的色彩模型从RGB 转换为灰阶、HLS、HSV...等。 因为程式中的OpenCV 会需要使用镜头或GPU&#xff0c;所以请使用本机环境( 参考&#xff1a;使用Python 虚拟环境) 或使用Anaconda Jupyter 进行实作( 参考&#x…
阅读更多...
火柴棒图python绘画

火柴棒图python绘画

使用Python绘制二项分布的概率质量函数&#xff08;PMF&#xff09; 在这篇博客中&#xff0c;我们将探讨如何使用Python中的scipy库和matplotlib库来绘制二项分布的概率质量函数&#xff08;PMF&#xff09;。二项分布是统计学中常见的离散概率分布&#xff0c;描述了在固定次…
阅读更多...
MUNIK解读ISO26262--系统架构

MUNIK解读ISO26262--系统架构

功能安全之系统阶段-系统架构 我们来浅析下功能安全系统阶段重要话题——“系统架构” 目录概览&#xff1a; 系统架构的作用系统架构类型系统架构层级的相关安全机制梳理 1.系统架构的作用 架构的思维包括抽象思维、分层思维、结构化思维和演化思维。通过将复杂系统分解…
阅读更多...
OZON生活家居用品爆款新品

OZON生活家居用品爆款新品

OZON生活家居用品爆款新品涵盖了多个方面&#xff0c;这些产品不仅满足了消费者对生活品质的追求&#xff0c;也反映了当前市场的热门趋势。以下是一些在OZON平台上备受关注的生活家居用品爆款新品&#xff1a; OZON生活家居用品爆款新品工具&#xff1a;D。DDqbt。COm/74rD T…
阅读更多...
昇思25天学习打卡营第17天|基于MobileNetv2的垃圾分类

昇思25天学习打卡营第17天|基于MobileNetv2的垃圾分类

今天学习的内容是利用视觉图像技术&#xff0c;来实现垃圾分类代码开发的方法。通过读取本地图像数据作为输入&#xff0c;对图像中的垃圾物体进行检测&#xff0c;并且将检测结果图片保存到文件中。 本章节主要包括8部分内容&#xff1a; 1、实验目的 1、了解熟悉垃圾分类应用…
阅读更多...
防御笔记第四天（持续更新）

防御笔记第四天（持续更新）

1.状态检测技术 检测数据包是否符合协议的逻辑顺序&#xff1b;检查是否是逻辑上的首包&#xff0c;只有首包才会创建会话表。 状态检测机制可以选择关闭或则开启 [USG6000V1]firewall session link-state tcp ? check Indicate link state check [USG6000V1]firewall ses…
阅读更多...
实践致知第12享：如何新建一个Word并设置格式

实践致知第12享：如何新建一个Word并设置格式

一、背景需求 小姑电话说&#xff1a;要新建一个Word文档&#xff0c;并将每段的首行设置空2格。 二、解决方案 1、在电脑桌面上空白地方&#xff0c;点击鼠标右键&#xff0c;在下拉的功能框中选择“DOC文档”或“DOCX文档”都可以&#xff0c;如下图所示。 之后&#xff0…
阅读更多...
光学传感器图像处理流程（二）

光学传感器图像处理流程（二）

光学传感器图像处理流程&#xff08;二&#xff09; 2.4. 图像增强2.4.1. 彩色合成2.4.2 直方图变换2.4.3. 密度分割2.4.4. 图像间运算2.4.5. 邻域增强2.4.6. 主成分分析2.4.7. 图像融合 2.5. 裁剪与镶嵌2.5.1. 图像裁剪2.5.2. 图像镶嵌 2.6. 遥感信息提取2.6.1. 目视解译2.6.2…
阅读更多...
沙龙回顾｜MongoDB如何充当企业开发加速器？

沙龙回顾｜MongoDB如何充当企业开发加速器？

数据不仅是企业发展转型的驱动力&#xff0c;也是开发者最棘手的问题。前日&#xff0c;MongoDB携手阿里云、NineData在杭州成功举办了“数据驱动&#xff0c;敏捷前行——MongoDB企业开发加速器”技术沙龙。此次活动吸引了来自各行各业的专业人员&#xff0c;共同探讨MongoDB的…
阅读更多...
vscode c++可以找到声明却无法自动补全

vscode c++可以找到声明却无法自动补全

这个问题折磨了我将近一个月&#xff0c;今天终于被解决了&#xff0c;特此记录 情景再现 事情的起因是我在学习华为的Ascend C算子&#xff0c;需要编写C代码。关于怎么下载库文件怎么编译之类的不是本文的重点&#xff0c;重点是自动补全。 我已经拿到库文件了&#xff0c…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023