Two Pointers

Algorithm Summary

Two-pointer algorithms scan an input with two indices moving in the same or opposite directions. They often exploit sorted order or replace nested scans with one linear pass.

Four recurring forms are:

1. Opposing pointers: start at both ends and move inward. Useful for sorted-array search and palindrome checks.
2. Same-direction pointers: the basis of sliding-window algorithms for contiguous ranges.
3. Fast and slow pointers: move at different speeds, especially for cycle detection and in-place compaction.
4. Backward pointers: write from the end when a forward merge would overwrite values that have not been processed.

Examples

Valid Palindrome II — LC 680

Move inward while the characters match. At the first mismatch, the string is valid if either skipping the left character or skipping the right character leaves a palindrome.

3Sum — LC 15

Sort the array. Fix one value with an outer loop, then use opposing pointers to find pairs that complete the sum. Skip duplicate fixed values and duplicate pointer values to avoid repeated triplets.

Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    int left = i + 1;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum < 0) left++;
        else if (sum > 0) right--;
        else {
            result.add(List.of(nums[i], nums[left], nums[right]));
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[right - 1]) right--;
            left++;
            right--;
        }
    }
}

Linked List Cycle — LC 141

Move fast two nodes for every one node moved by slow. If a cycle exists, the fast pointer eventually laps the slow pointer; otherwise it reaches null.

Linked List Cycle II — LC 142

After the pointers meet inside the cycle, move one pointer to the head. Advance both one step at a time; their next meeting point is the cycle entrance.

head ── distance a ──▶ entrance ── distance b ──▶ meeting point
                         ▲                         │
                         └──── remaining cycle ────┘

Remove Element — LC 27

Use a slow pointer as the next write position. The fast pointer scans every value and copies only values that do not equal val.

Reverse Linked List — LC 206

Maintain previous, current, and next. Save the next node before redirecting current.next to previous.

Intersection of Two Linked Lists — LC 160

Advance one pointer through list A then B, and the other through B then A. The equalized total path lengths make them meet at the intersection or both reach null.