1. Concept
2. Two Pointer Problems
   1. Two Pointer
   2. Fast Slow Pointer

Concept

Two pointers are used to scan in two directions during traversal, achieving the respective algorithmic goals.

In a broad sense, two pointers refer to problems solved by traversing with two variables in linear structures.

In a narrow sense:

• For arrays, it refers to problems solved by two variables moving in opposite directions on the array.
• For linked lists, it refers to problems solved by two variables moving in the same direction on the linked list, also known as the “fast-slow pointer” problem.

Two Pointer Problems

Two Pointer

The two-pointer approach defines the leftmost index as the left pointer (left) and the rightmost index as the right pointer (right), traversing the array from both ends towards the middle.

The two-pointer approach is suitable for sorted arrays and strings.

The time complexity of the two-pointer approach is .

LeetCode Problem 21

This problem requires rearranging the order of the array by odd and even numbers. We can use the left pointer to find odd numbers and the right pointer to find even numbers. When the left pointer finds an even number and the right pointer finds an odd number, swap the two numbers. The code is as follows:

vector<int> exchange(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        while(l < r && nums[l] % 2 == 1) l++;
        while(l < r && nums[r] % 2 == 0) r--;
        swap(nums[l], nums[r]);
    }
    return nums;
}

LeetCode Problem 57

This problem requires finding pairs of numbers that sum to . Since the array is already sorted in this problem, we can determine:

If the pair , then .

Similarly, if , then .

Therefore, this problem can also be solved using the two-pointer approach. When , move to the right; otherwise, if , move to the left. The code is as follows:

vector<int> twoSum(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    vector<int> ans;
    while (l < r) {
        while (l < r && nums[l] + nums[r] < target) l++;
        while (l < r && nums[l] + nums[r] > target) r--;
        if (nums[l] + nums[r] == target) {
            ans.push_back(nums[l]);
            ans.push_back(nums[r]);
            return ans;
        }
    }
    return ans;
}

Fast Slow Pointer

The fast-slow pointer defines a pair of pointers with different speeds in the sequence to solve one-way sequence problems.

The time complexity of the fast-slow pointer approach is , and the space complexity is .

LeetCode Problem 141

This problem requires determining whether a linked list has a cycle. We can define a fast pointer and a slow pointer, and then move them. If the fast pointer catches up with the slow pointer, it means the linked list definitely has a cycle. The code is as follows:

bool hasCycle(ListNode *head) {
    ListNode *p1 = head, *p2 = head;
    do {
        if (p1 && p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        else return false;
    } while(p1 != p2);
    return true;
}

LeetCode Problem 142

This problem requires finding the first node of the cycle while determining if there is a cycle. We can reason based on the condition that the fast pointer’s speed is always twice that of the slow pointer.

Assuming the fast and slow pointers meet at point , at this point, the distance the slow pointer has traveled should be , while the fast pointer has traveled .

Since the fast pointer’s speed is twice that of the slow pointer, we have:

,

which implies .

Therefore, when the fast and slow pointers meet, the distance from the meeting point to the entry point of the cycle is always . We can then use another pointer to find the entry point of the cycle while updating and the slow pointer. When they meet, the meeting node is the entry point of the cycle. The code is as follows:

ListNode *detectCycle(ListNode *head) {
    ListNode *p1 = head, *p2 = head;
    do {
        if (p1 && p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        } else return NULL;
    } while (p1 != p2);
    ListNode *cur = head;
    while (cur != p1) {
        cur = cur->next;
        p1 = p1->next;
    }
    return cur;
}