一：课前讲解
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针
对于单链表来说，大部分技巧都属于快慢指针，在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针。
二：快慢指针的使用技巧
例题①：删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
高效解决这道题就要用到快慢指针技巧
我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[0…slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0…slow] 就是整个数组去重之后的结果。
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
}
例题②：删除排序链表中的重复元素
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
算法执行的过程请看下面这个 GIF：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// 千万不要进坑
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null){
if(fast.val != slow.val){
slow.next = fast;
slow = fast;
}
fast = fast.next;
}
slow.next = null; // //这一步很重要，不要忘记
return head;
}
}
例题③：移除元素
https://leetcode.cn/problems/remove-element/
题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
这和前面说到的数组去重问题解法思路是完全一样的。
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0;
int slow = 0;
while(fast<nums.length){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
例题④：合并两个有序链表 剑指 Offer
合并两个有序列表 ，首先需要一个指针永远指向第一个节点，两一个指针需要不断的向后走进项比较 直到有一条链表为空的时候，另一条链表的数据全部放过来
public void mergeTwoLists(ListNode n1,ListNode n2){
ListNode tNewNode = new ListNode(0); //定义的头结点
ListNode tempNode = tNewNode; //定义的指针
while (n1 !=null && n2 !=null){
if(n1.getVal() < n2.getVal()){
tempNode.setNext(n1);
n1 = n1.getNext();
}else {
tempNode.setNext(n2);
n2 = n2.getNext();
}
tempNode = tempNode.getNext();
}
if(n1 == null){
tempNode.setNext(n2);
}
if(n2 == null){
tempNode.setNext(n1);
}
}
例题⑤：链表的分解
https://leetcode.cn/problems/partition-list/
在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。
整体逻辑和合并有序链表非常相似，细节直接看代码吧，注意虚拟头结点的运用：
ListNode partition(ListNode head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode p1 = dummy1, p2 = dummy2;
// p 负责遍历原链表，类似合并两个有序链表的逻辑
// 这里是将一个链表分解成两个链表
ListNode p = head;
while (p != null) {
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
p1.next = p;
p1 = p1.next;
}
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;
}
// 连接两个链表
p1.next = dummy2.next;
return dummy1.next;
}
例题⑥：删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//这个是必须有的，建立这个假节点是为了防止只有一个数据的情况
ListNode d = new ListNode(-1);
d.next = head;
ListNode p1 = d;
ListNode p2 = d;
//让p1先走n步
for(int i = 0;i<n;i++){
p1 = p1.next;
}
//p1和p2同时走
while(p1.next!=null){
p1 = p1.next;
p2 = p2.next;
}
p2.next = p2.next.next;
return d.next;
}
}
例题⑦：链表的中间结点
https://leetcode.cn/problems/middle-of-the-linked-list/
我们让两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
class Solution {
ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
//注意顺序
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}
}
例题⑧：判断单链表是否包含环并找出环起点
/**
* 判断链表是否有环
* @return
*/
public boolean HasCycle() {
ListNode fast = head; //走在前边的节点
ListNode slow = head; //走在后边的节点
//这里的判断条件之所以是这样，是因为要保证不成环的情况下依旧不报错
while ((fast != null)&&(fast.next !=null)) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
/**
* 判断链表是否有环，并找出成环的位置
* @return
*/
public void HasCycle() {
ListNode fast = head; //走在前边的节点
ListNode slow = head; //走在后边的节点
//这里的判断条件之所以是这样，是因为要保证不成环的情况下依旧不报错
while ((fast != null)&&(fast.next !=null)) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
slow = head;
while (slow != fast){
fast = fast.next;
slow = slow.next;
}
System.out.println(slow.value);
return; // 别忘了这个return ，否则会出现死循环
}
}
}
我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：
fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：
所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。
例题⑨：相交链表
https://leetcode.cn/problems/intersection-of-two-linked-lists/
三种解法：
1.使用Map
2.链表相连，将headA的尾指针指向haedB的头，转换成环形链表，就形成了和上题一样，去找成环的初始节点。但是注意这道题并不让我们改变其原始结构。
3.双指针
如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。
解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。
所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：
那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？
这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。
public class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) {
p1 = headB;
}else{
p1 = p1.next;
}
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null){
p2 = headA;
}else{
p2 = p2.next;
}
}
return p1;
}
}
三：左右指针的使用技巧
例题①：二分查找
https://blog.csdn.net/weixin_39038328/article/details/136516247
具体讲解思路看这里
例题②：两数之和
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整 sum 的大小：
int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}
例题③：翻转数组
https://leetcode.cn/problems/reverse-string/文章来源：https://www.toymoban.com/news/detail-838569.html
void reverseString(char[] s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length - 1;
while (left < right) {
// 交换 s[left] 和 s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
例题④：回文串判断
首先明确一下，回文串就是正着读和反着读都一样的字符串。
比如说字符串 aba 和 abba 都是回文串，因为它们对称，反过来还是和本身一样；反之，字符串 abac 就不是回文串。
现在你应该能感觉到回文串问题和左右指针肯定有密切的联系，比如让你判断一个字符串是不是回文串，你可以写出下面这段代码：文章来源地址https://www.toymoban.com/news/detail-838569.html
boolean isPalindrome(String s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
到了这里，关于算法学习---双指针算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
