Two Pointer
Two-pointer technique is commonly used to solve array, string and linked list problem. It often solves the problem in place. We have classified the two-pointer questions by its templates. The two pointer questions include sliding window, partition(merge sort, quick sort), binary search, fast and slow pointer, and left and right pointer problems. In this article, we will only describe fast and slow pointer, and left and right pointer .
The main thought in this article is originated from labuladong, and jiuzhang
Fast and Slow Pointer (Hare & Tortoise):
- It is mostly applied on the linked list or sorted array. The question usually requires O(1) extra space, i.e., no extra spaces.
- It is mostly used by single linked list, whose pointer can not traverse reversely.
- The slow pointer represents the last qualified result before fast pointer. The fast pointer will enumerate all elements. Faster pointer will always move in each iteration no matter slow pointer moves or not. The slow pointer will move only when fast pointer’s element satisfied some requirements. Such moving way can make sure the slow pointer always fall behind the fast pointer.
- Since the slow pointer represents the last qualified result, the slow pointer can start from the first element when the first element is a valid result. Slow pointer can also start before the first element such as dummy head or null when the first element may or may not be a valid result.
- Since the fast pointer represents all possible elements, the fast pointer usually starts from the first element.
- The fast and slow pointer is similar to sliding window. The difference is slow pointer is usually moving one step forward for each right element. In most cases, we need to consider what condition the fast pointer needs to satisfy to make slow pointer move. (slow pointer 什么时候走)。
Left and Right Pointer:
- It is often used for searching a group of elements satisfying some requirements in sorted array or linked list. The group can be a pair, 3 elements or even a sub array.
- In each iteration, either left and right pointer will move.（要么left pointer走一步， 要么right pointer走一步）。
Two Different Array Pointers:
The two pointers are moving on two different array or list.