双指针技巧套路框架

双指针技巧分为两类，一类是“快、慢指针”，一类是“左、右指针”。前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分搜索。

快、慢指针的常用算法

1.判定链表中是否有环？设置快、慢指针解决。
solution：

1
2
3
4
5
6
7
8
9
10
11
boolean hasCycle(ListNode head){
    ListNode fast, slow;
    //初始化快慢指针只像头节点
    fast = slow = head;
    while(fast != null && fast.next != null){
        fast = fsat.next.next;
        slow = slow.next;
        if(fast == slow) return true;
    }
    return false;
}

2.已知链表中含有环，返回这个环的起始位置
solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode detectCycle(ListNode head){
    ListNode fast, slow;
    fast, slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) break;
    }
   slow = head;
   while(slow != fast){
       fast = fast.next;
       slow = slow.next;
   }
   return slow;
}

可以看到，当快、慢指针相遇时，让其中任何一个指针只像头节点，然后让两个指针以相同的速度前进，再次相遇时所在的节点位置就是环开始的位置。//数学逻辑推理
3.寻找无环单链表的中点
solution：

1
2
3
4
5
6
while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
}
//slow就是我们要求的中点
return slow;

注：当链表长度是奇数时，slow 恰巧停在中点位置；当链表的长度是偶数时，slow 最终的位置是中间偏右。
4.寻找单链表的倒数第k个元素
solution：

1
2
3
4
5
6
7
8
9
10
ListNode slow, fast;
slow = fast = head;
while(k-- > 0){
    fast = fast.next;//快指针先走k步
}
while(fast != null){
    slow = slow.next;
    fast = fast.next;
}
return slow;

快指针先走k步，然后慢指针、快指针一起走，直到快指针走到头了，慢指针就走到倒数第k个元素了。

左、右指针的常用算法

左、右指针一般运用在数组问题中，一般初始化为left = 0, right = len(nums) - 1 。
1.二分搜索（略，见下一小节）
2.两数之和（略）
3.反转数组（略）
4.滑动窗口算法（略，见下下小节）
tips：一般数组有序就可以考虑左、右双指针。