双指针
双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。
一类是「快慢指针」,另一类是「左右指针」。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。
快慢指针
快慢指针也是双指针,但是两个指针从同一侧开始遍历数组,将这两个指针分别定义为
快指针(fast)
和慢指针(slow)
,两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如fast每次增长两个,slow每次增长一个。例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等,都是可以使用快慢指针解决。
解决的问题:
- 计算链表的中点:快慢指针从头节点出发,每轮迭代中,快指针向前移动两个节点,慢指针向前移动一个节点,最终当快指针到达终点的时候,慢指针刚好在中间的节点。
- 判断链表是否有环:如果链表中存在环,则在链表上不断前进的指针会一直在环里绕圈子,且不能知道链表是否有环。使用快慢指针,当链表中存在环时,两个指针最终会在环中相遇。
- 判断链表中环的起点:当我们判断出链表中存在环,并且知道了两个指针相遇的节点,我们可以让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。
- 求链表中环的长度:只要相遇后一个不动,另一个前进直到相遇算一下走了多少步就好了
- 求链表倒数第k个元素:先让其中一个指针向前走k步,接着两个指针以同样的速度一起向前进,直到前面的指针走到尽头了,则后面的指针即为倒数第k个元素。(严格来说应该叫先后指针而非快慢指针)
示例代码-环形链表问题:
1 | public boolean hasCycle(ListNode head) { |
LeetCode题目示例
- 【141. 环形链表】 –简单
- 【142. 环形链表 II】 –中等
- 【26. 删除排序数组中的重复项】
- 【19. 删除链表的倒数第N个节点】 –中等
左右指针(双向指针)
对撞指针是指在有序数组中,将指向最左侧的索引定义为
左指针(left)
,最右侧的定义为右指针(right)
,然后从两头向中间进行数组遍历。对撞数组适用于有序数组,也就是说当你遇到题目给定有序数组时,应该第一时间想到用对撞指针解题。
解决的问题
二分查找问题
n数之和问题:比如两数之和问题,先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。
伪代码如下:
1 | private static void test(List<Integer> list) { |
LeetCode题目示例
- 【167. 两数之和 II - 输入有序数组】 – 简单题
- 【15. 三数之和】 –中等
- 【881. 救生艇】 –中等题