Two pointer approach is extensively used since it provides \(\mathcal{O}(n)\) time and \(\mathcal{O}(1)\) space. It is especially tailored for linked list problems which often involves at least one pointer for linked list traversal. Fast-slow pointer pair is one representative instance of two pointer approach:

141 Linked List Cycle

If there is a cycle, then fast pointer with catch up with slow pointer. O(1) memory and O(n) time.

142 Linked List Cycle II

\(>141\) we need to locate where the cycle starts. After 2 pointers meet, reset one pointer and proceed 2 pointers both one step at a time until they meet again.

876 Middle of the Linked List

Return directly when fast pointer reaches the end.

19 Remove Nth Node From End of List

The fast node offset by N and then both proceed with the same speed

160 Intersection of Two Linked Lists

Brute force (\(\mathcal{O}(mn)\) time \(\mathcal{O}(1)\) space) or hash table approach (\(\mathcal{O}(m+n)\) time, \(\mathcal{O}(max(m,n))\)) space complexity approach are simple. With two pointer approach, we could get \(\mathcal{O}(m+n)\) time and \(\mathcal{O}(1)\) space: first reach the end of linked list A and form a cycle by connecting the tail of linked list A to head of B. Now it is reduced to problem 142 Linked List Cycle II, remember to disconnect A tail and B head at the end.

For general linked list problems, often we need dummy/temp pointers besides the iterator pointer to avoid losing states during inplace modification. The usage of two pointer is explicit when two linked lists are involved.

82 Remove Duplicates from Sorted List II

Unlike 83 Remove Duplicates from Sorted List, we need a dummy prev pointer to record the node before the repeating chain.

21 Merge Two Sorted Lists

Remember to consider the edge cases when one or both of the given linked lists are NULL, also need to record the head and keep it static while let the iterator pointer of the new list proceed.

206 Reverse Linked List

Need a dummy prev node pointed by curr.next during each iteration.

92 Reverse Linked List II

\(\approx 206\) with more temporary variables.

25 Reverse Nodes in k-Group

The problem is tagged as hard. The key is to modularize a helper API from 206 Reverse Linked List which reverses a given linked list section (ListNode* reverse(ListNode* prev, ListNode* end)).

24 Swap Nodes in Pairs

Again, the key is to maintain a dummy prev node pointer for the pair to swap. For each swap, use tmp pointers to avoid losing states and then swap freely.

61 Rotate List

Equivalent to rotate by \(k\%n\)

143 Reorder List

Three steps: use fast-slow pointer pair to find the point to split, then reverse the second half, finally merge.

86 Partition List

Maintain 2 separate linked lists, and append to one of them during the iteration depending on the inequality before final concatenation.

2 Add Two Numbers

Straightforward since least significant number comes first.

Besides linked list, two pointer approach is also prevalent in problems over array-like data structures, often in the form of left and right pointer pair. Binary search is one concrete instance.

704 Binary Search

Basic binary search to find the index of target value. Use left + (right - left) / 2 rather than (left + right) / 2. while condition and left/right pointer update depend on whether the search set boundary is inclusive or exclusive (which is flexible).

35 Search Insert Position

Same as 704, but return left rather than -1 at the end

34 Find First and Last Position of Element in Sorted Array

When finding the first/last position of the target value, remember to check if the right/left boundary is exceeded*

875 Koko Eating Bananas

Optimize brute force search with binary search of first position of the value satisfying the constraint

1011 Capacity To Ship Packages Within D Days

Same as 875, but with different search boundary and helper constraint satisfying function

Sliding window approach is slightly more complicated and commonly used in substring problems. Unlike binary search, left/right pointer pair gets initialzied to the starting point, and the core loop is to iterate the right pointer.

76 Minimum Window Substring

Inside iteration: update metadata for the bigger window, shrink window by left pointer increment, check solution validity and update return. Hash map is needed as char counter (part of metadata) for this problem.

438 Find All Anagrams in a String

\(\approx 76\) except that the window length is fixed.

3 Longest Substring Without Repeating Characters

567 Permutation in String

\(\approx 76\) first find the shortest substring and return if no redundant chars. Or add an unmatch counter additionally to directly check the solution validity inside the left pointer loop.

There are other examples showing the usage of two pointer approach for arrays:

167 Two Sum II - Input array is sorted

Left pointer at start pointing and right pointer at the end.

344 Reverse String

Swap objects pointed by left/right pointer pair until they meet at the middle point.

27 Remove Element

Fast/slow pointer pair.

26 Remove Duplicates from Sorted Array

80 Remove Duplicates from Sorted Array II

\(\approx 26\) we allow up to 2 duplicates, hence an extra counter is needed.