之前的文章中提到了最基础简单的二分法，其实是双指针算法的一种应用
那么今天我们进阶一点介绍双指针算法
【符号说明】
❤️重点
🧡备注
💙问题
本文稍有难度，其实是想先讲相对简单排序算法的，但刚好讲完了二分，那就趁热打铁，把双指针也讲了
🧡如果还不明白【指针】的概念，建议自行百度学习，这不是算法教程涉及的概念
🧡本文需要具备【链表】的基础，这是属于【数据结构】的知识，故本文不作说明，基础薄弱的可自行百度，查缺补漏再回头阅读本文
考虑到零基础读者，上两个知识本文作个简单介绍，但仅仅是介绍，具体的内容需要自行学习
❤️指针
首先要明白一个概念，计算机如何存放数据？
对于想要长期存储的数据，比如一个软件，会存在硬盘中，然而运行中还会产生许多暂存的数据，关机后就没了，那就会存放在【运行内存】中（简称内存）
所谓指针，就是一个引用内存地址的数据（计算机的运行数据是暂存在运行内存中，通过一个个“地址”进行编号，指针相当于一个编号索引）
在部分编程语言中会设计显式指针（如c，cpp，go），而部分语言使用隐式/高级指针（java，py，js），区别是有无明确的【指针修饰符】（多为&），后者无需自己管理内存索引，可以称为高级指针
💙那么没有显式指针的编程语言怎么体现呢？
答案是【引用数据类型】，例如数组，对象等结构
例如arr[0]，这里的0就是一个指向内存地址的索引，不严格的来说，也可以算作指针
❤️链表
一种数据结构，存着自身的值和下一个链表的索引（可以是空值），本文简单实现了一个ListNode（节点）当链表使用了
环是指一个链表的最后一个节点的next指向回了前面的元素，形成了一个“环”
💙那么什么又是【双指针】呢？
顾名思义，双指针其实就是两个指针，从算法的角度来说，双指针一般有两种，分别是快慢和左右，我们一一讨论：
❤️快慢指针
这种情况多应用于链表和数组，我们让两个指针（A，B）以不同的速度遍历
再直白一点，a每次走2步，b每次走1步，我们来看个简单模型
💙问：请判断一个链表是否存在【环】
不难解决，如果没有环，那么快指针总是先到末尾节点，那么它的next就一定是null，然后退出循环，返回false
但是如果有【环】存在，那么一个不会出现next的值是null的情况，所以快指针一定会追上慢指针一圈，所以当它们重合的时候就可以返回true了
【图二】
💙问：求一个有环链表出现环的位置
学会了第一问这题就不难，只需要稍微调整上面的代码即可
【图三】
仔细想想，一开始不是快指针比慢指针多1倍距离，假设链表起点到相遇点有y步，相遇时慢指针走了x步，快指针就是2x步
那么链表起始到环就是x-y
快慢指针相遇的时候，快指针多走了x步，所以只要在相遇时，两个指针改为一样速度（步长），并且其中一个回到开头，那么在下次相遇时就能得到相遇点
💙问：求链表中间节点
这题基础解法是先遍历一遍链表获取长度，再按长度的一半循环获取中间节点
然而使用双指针会让这题简单不少：
快指针速度刚好是慢指针的2倍，所以当快指针到末尾时，慢指针指向的就直接是中间节点！
【图四】
❤️左右指针
这种情况也不难理解，一个在开头，一个在末尾，就称之为左右指针
是不是想到了上一篇【二分法】？
#【原创】【算法之旅】二分查找法#
🎉如果你是按顺序来的，那么恭喜，你已经学过左右指针的基本应用了
当然，双指针的“最高境界”【滑动窗口】我们还没讲解，鉴于难度我打算往后放放
那么本文就到此结束啦，有疑问也欢迎评论区留言
[彩虹]pluie
[彩虹]2023-06-18
相关文章
