双指针可以解决的几类问题（持续整理）

80 阅读 0 评论 53 点赞

我是靠谱客的博主机灵摩托，最近开发中收集的这篇文章主要介绍双指针可以解决的几类问题（持续整理），觉得挺不错的，现在分享给大家，希望可以做个参考。

一、获取倒数第k个元素

**原理：**设有两个指针p、q，p指向头结点，q顺着next移动k次，指向第k+1个结点，p和q之间的距离为k。当q指向空结点时，p指向的元素即为倒数第k个元素。
**代码实现思路：**用while循环让快指针先走k步，再用while循环让快慢指针同时走。
要点：

3.1 定义链表的方式，即let fast=head;let slow=head；

3.2 必须考虑输入空数组的情况，即if(!head) return null；

3.3 返回指针对应的值用val关键字，即slow.val。

二、获取中间位置的元素（题目876）

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

**原理：**设有两个指针p、q，p一次走一格，q一次走两格。这里要考虑链表长度的奇偶，链表为奇数时，p在最中间，q在结尾；链表为偶数时，p在中间结点的右边那个，q.next为null。类似思路还可以找到1/3处节点位置，1/5处节点位置，调整快指针的速度即可。
要点：

2.1 要考虑奇偶数两种情况。

三、判断链表是否存在环（题目141）

**原理：**设有两个指针p、q，p一次走一格，q一次走两格。如果某一次p=q，则说明链表存在环。
**遇到的报错：**TypeError: Cannot read properties of null (reading ‘next’)这个报错表示我有条件没写完整，有时候next已经不存在了，但是因为我没有写相应的条件判断所以还在读取。

四、判断环形链表的长度

**原理：**设有两个指针p、q，p一次走一格，q一次走两格。快慢指针相遇后继续移动，直到第二次相遇，两次相遇间的移动次数即为环形链表的长度，因为q比p快了整整一圈。

五、相交链表（题目160）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

**原理：**设相交链表长度为c，长链表A、短链表B分开时各自的长度为a、b，则A的长度为a+c，B的长度为b+c。设有两个指针p、q对两个链表分别进行遍历，短链表B先遍历完，将其指向长链表A；A遍历完后，将其指向B。两个指针继续向下遍历，当它们重合的时候，指向的即为相交结点。该举措为消除长度差。
要点：

2.1 遍历完即为指向null；

2.2 可以使用三元表达式，如p = p === null? headB:p.next。

六、反转链表（题目206）

七、反转元音字母（题目345）

**原理：**使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。
要点：

2.1 js中in关键字的使用：

所以这道题还是用has()关键字更合适，has()要搭配new Set()，如果只是let arr = [数组]会报错arr is not a function，因为arr是Object。

2.2 ES6中交换数组的方法：[newS[i],newS[j]] = [newS[j], newS[i]]，不需要再储存中间值。

八、移动零（题目283）

**原理：**设有两个指针fast、slow，碰到0，fast往前挪一格；碰到的不是0，则把当前值赋给slow，fast、slow各往前挪一格。当fast.next=null时，将剩下的数字都通过遍历赋值为0。
要点：

2.1 这题不是链表，是数组！所以和head、next没有关系，直接let fast = 0，判断条件也直接while(fast < nums.length)。

九、两数之和（题目167&633）

**原理：**在递增数组中找出两个数，使它们的和为 target。使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；

如果 sum > target，移动较大的元素，使 sum 变小一些；

如果 sum < target，移动较小的元素，使 sum 变大一些。

要点：

2.1 let sum = numbers[p] + numbers[q];一定要写在循环条件中；

2.2 看清要求，例如167.两数之和要求return [p+1,q+1]；633.两数平方和中p可以等于q。

十、结合递归判断回文字符串（题目680）

**原理：**使用双指针，令一个指针从左到右遍历，一个指针从右到左遍历，两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串就是具有左右对称性质的回文字符串。本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。
要点：

2.1 条件应该写为let a = 0;b = s.length - 1; while(a<b){}，for循环不能同时声明两个变量，其语法为for（单次表达式;条件表达式;末尾循环体）；

2.2 创建函数可以使用ES6语法中的箭头函数var judgeValidPalindrome = (s,a,b) => {}。

十一、归并两个有序数组（题目88）

**原理：**设有三个指针i、j、k，i = nums1.length -1，j = nums2.length -1，k = nums1.length + nums2.length -1，从尾遍历，比较i和j的大小，进行覆盖。
要点：

2.1 条件为i>=0||j>=0，赋值后进行自减处理可简化为nums1[k--] = nums2[j--]，在for循环中，k--和--k的输出是一致的。

十二、比较版本号（题目165）

**原理：**将两个版本号分别按照点分割开返回成两个数组，设有两个指针x、y分别对它们进行遍历，并将字符串转换为整数进行比较（使用parseInt，parseInt是用于将字符串根据基数转换成整数）。
要点：

2.1 首先要用split('.')将版本号分割为数组。

十三、实现快速排序

**原理：**将第一个元素的索引设为low，最后一个元素的索引设为high；设有两个指针i、j，选定最后一个元素作为pivot，let i = low, j = low，如果j指向的元素比pivot小，则i、j互换，i++;j++，如果j指向的元素比pivot大，j++。最终，将pivot元素和最后i指针指向的元素进行交换。