浅谈双指针技巧(一)---通过双指针判断链表成环问题
2022/9/7 23:26:44
本文主要是介绍浅谈双指针技巧(一)---通过双指针判断链表成环问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
双指针是算法中非常重要的一个解决问题的思路。
双指针顾名思义,就是有两个指针。根据双指针的方向及速度,我们一般将双指针分为以下几种场景
1、快慢双指针
2、左右双指针
所谓快慢双指针是指,两个指针,一个快指针,一个慢指针,按照相同的方向,从链表(或数组)的一侧移动到另外一侧的场景。
如下图:
而左右双指针,是指两个指针,分别指向链表的左右两侧,相向而行。
如下图:
快慢双指针一般用于查找链表成环、特殊位置的节点、滑动窗口等问题。
左右双指针一般是解决二分查找等问题
虽然都归结为双指针,但其实他们的思想各不相同,甚至不同场景的问题,思想都不同,只是由于都用到了两个指针,将这类算法技巧统称为双指针。
本文我们重点来看快慢双指针的经典问题:(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )
判断链表是否成环
力扣 141. 环形链表 (https://leetcode.cn/problems/linked-list-cycle/)
给你一个链表的头节点 head ,判断链表中是否有环。
所谓的链表存在环,也就是下边这个样子,没有某个节点的next指向null:
这个场景,如果环的结构不大的话,我们可以直接将结果直接存放到一张hash表中,然后指针从头部依次遍历,判断新指向的节点是否已经存在于hash表中。
如果hash表中存在,则判定为当前链表存在环,否则将该节点加入到hash表中,继续遍历。直到遇到链表的尾结点(next指针指向null)时,判定为不存在环。
这种思想的代码这里就不写了。(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )
如果数据规模小的话,这个办法没有问题,甚至会很快。但是如果数据规模很大的话,这就会导致没有足够的内存来存放这个hash表。
如果不采用临时缓存的办法,那么应该咋么解决呢?来看看快慢双指针的思路
快指针Fast、慢指针Low,同时指向头结点,然后均向像队尾移动,区别是快指针每次移动两个节点,慢指针每次移动一个节点。
如果链表不存在环,那么经过不断的移动,快指针肯定会找到队尾元素。
如下图 :
这里很好理解。
如果链表存在环,那么经过不断的移动,快慢指针最终会相遇,同时指向某个节点。
如下图:
这是为什么呢?快指针再次跨过慢指针我们可以理解,为什么会恰好相遇在某个节点,而不是每次都恰好越过慢指针呢?
答案是并不会,原因是:(防盗连接:本文首发自http://www.cnblogs.com/jilodream/ )
快慢指针经过移动后,同时处在环中,假设快指针通过由于速度快,再次赶上慢指针的节点差距为N。由于快指针每次比慢指针快一步,导致N每次逐渐缩小1,因此这个N=1。
感兴趣的读者可以自己在纸上画一下。
下面我们直接来看代码
1 public boolean hasCycle(ListNode head) { 2 if (head == null) { 3 return false; 4 } 5 ListNode fast = head; 6 ListNode low = head; 7 while (true) { 8 if (fast == null) { 9 return false; 10 } 11 if (fast.next == null) { 12 return false; 13 } 14 if (fast.next.next == null) { 15 return false; 16 } 17 fast = fast.next.next; 18 low = low.next; 19 if (fast == low) { 20 return true; 21 } 22 } 23 }
这篇关于浅谈双指针技巧(一)---通过双指针判断链表成环问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署