LeetCode 系列——双指针问题 。

关于 LeetCode 系列有段时间没有逐题更新了 ，还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ，准备系统的讲讲数据结构相关知识点 。

刷 LeetCode 那点事 ！

今天想要分享的是在刷题中频繁遇到的一个知识点——双指针问题 。杠精读者有没有 ？

指针 ？博主你又在扯蛋 ，Python 没有指针好的伐 ！

的确是 ，Python 中没有指针的概念 。刷前几题的时候遇到过链表问题 ，有读者就对链表问题表示困惑 ，其实根本原因就在这 。Python 中用的就是模拟指针 ，所以链表也是模拟链表哟 。

双指针说白了就是两个指针指向两个地址 ，可能是移动速度不同 ，可能是指向不同的节点（元素）。用这种方式去解决一些实际问题 。

⒈

合并问题 。比如给定两个有序数组 ，要求将两个有序数组进行合并 ，合并成一个有序数组 。其实有点类似之前刷过的第 4 题 ：

LeetCode | 两个有序数组的中位数

当时写的代码不够优化美观 ，但是这类合并问题都可以用到双指针思路解决噢 。

• 分别定义两个 “指针” ，指向两个数组（list_1；list_2）的首位 。再定义一个新数组（列表list_3）用于存储最终结果 。
• 将指针指向的两个元素进行比较 ，将较小的元素 copy 到 list_3 中 。
• 将元素较小的数组指针右移一位 ，继续比较 。直到 list_1 或者list_2 中某一个所有元素都遍历完 ，将另一个剩下的所有元素 copy 到 list_3 即可 。

⒉

链表是否有环问题 。链表也是我们所常见的一个数据结构了 ，判断一个链表是否有环就可以用双指针思路解决 。这个在 LeetCode 的第 141 题 。

• 定义两个指针 ，一快一慢 。比如慢指针一次移动 1 个位置 ，快指针移动 2 个 。
• 初始快慢指针放在一个位置 ，并开始循环移动 。
• 如果有环 ，那么随着移动的进行 ，终有快指针经过环遇到并超过慢指针的时候 ，那么这就可以用来判断是否存在环的依据啦 。

⒊

原地移除重复元素 。这也是 LeetCode 上比较经典也比较容易的问题 。给定一个排序数组 ，要求删除其中的重复项 。同类型的还有删除给定值 。这两题在 LeetCode 的第 26 和第 27 题 ：

No.26 删除排序数组中的重复项

No.27 移除元素

⒋

奇偶排序 。一个公司的面试题 ，给定一个数组 ，有奇数也有偶数 ，要通过处理将奇数放在左边 ，偶数在右边 。这个也可以通过双指针思路进行解决 。

• 定义两个指针 ，分别指向首尾 。
• 左边指针元素若为奇数（取模得 1）指针右移 ，直到指向第一个偶数元素 。
• 右边指针元素若为偶数 （取模得 0）指针左移 ，直到指向第一个奇数元素 。
• 将上述两个指针指向元素互换 。
• 重复上述步骤 ，直到指针指向同一个元素 。

参考代码如下 ：

⒌

关于双指针的应用还有很多呀 ，欢迎读者小伙伴们一起留言区补充交流 。