链表的双指针问题

有环无环的问题

判断一个链表有没有环的方法一般是使用一个慢指针和一个快指针,慢指针一次走一步,快指针一次走两步,这样如果链表有环的话,快慢指针是会相遇的。

同时使用这个方法也可以求链表环的入口,这就涉及到一个结论,从链表的头部到环的入口,与相遇的点到环的入口的距离是一样的(或者少了n圈)。

快慢指针的方法可以用来求无环链表的中点问题,或者求链表的倒数第n个节点这样的问题。

Linked List Cycle

Linked List Cycle II

Remove Nth Node From End of List

数组的双指针问题

修改数组问题,比如去重

这些题一般是要求使用O(1)的空间复杂度来将以前的数组变成一个要求的数组。比如去重,就是使用一个指针来标记下一个元素的正确位置,另一个指针去遍历数组。

Move Zeroes

Sort Colors

滑动窗口问题

使用一前一后两个指针来标记一个符合需求的窗口。

Longest Substring Without Repeating Characters

对撞指针问题

设置一前一后两个指针,然后根据条件来移动前面的指针或者后面的指针,知道两个指针相遇。

3Sum

Container With Most Water