Double pointer algorithm

Posted on Edited on In Waline:

Principle

Fast and slow pointer

The two-pointer technique is further divided into two categories, one is “fast and slow pointers”, and the other is “left and right pointers”. The former mainly solves problems in linked lists, such as typically determining whether a linked list contains a ring; the latter mainly solves problems in arrays (or strings), such as binary search.

The fast and slow pointers are generally initialized to point to the head node of the linked list. When advancing, the fast pointer is fast in front and the slow pointer is slow in the back, which skillfully solves some problems in the linked list.

Determine whether the linked list contains a ring.

This should belong to the most basic operation of linked lists. If readers already know this technique, they can skip it.

The characteristic of a single linked list is that each node only knows the next node, so a pointer cannot determine whether the linked list contains a ring.

If there is no ring in the linked list, then this pointer will eventually encounter a null pointer to indicate that the linked list is at the end, which is good to say, it can be judged that the linked list does not contain rings.

1
2
3
4
5
boolean hasCycle(ListNode head) {
    while (head != null)
        head = head.next;
    return false;
}

However, if the linked list contains a ring, then the pointer will fall into an infinite loop, because there is no null pointer as the tail node in the ring array.

The classic solution is to use two pointers, one running fast and the other running slow. If it does not contain a ring, the fast pointer will eventually encounter null, indicating that the linked list does not contain rings; if it contains rings, the fast pointer will eventually exceed the slow pointer once and meet the slow pointer, indicating that the linked list contains rings.

1
2
3
4
5
6
7
8
9
10
11
boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast  slow) return true;
    }
    return false;
}

Knowing that the linked list contains a ring, return the starting position of this ring.

This problem is not difficult at all. It is a bit like a brain teaser. Let’s look directly at the code first.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast  slow) break;
    }
    //The above code is similar to the hasCycle function
    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

You can see that when the fast and slow pointers meet, let either pointer point to the head node, and then let them both move forward at the same speed. When they meet again, the node position is the position where the ring starts. Why is this?

At the first encounter, if the slow pointer slow took k steps, then the fast pointer fast must have taken 2k steps, that is, k steps more than slow (that is, the length of the ring).

Let the distance between the meeting point and the starting point of the ring be m, then the distance between the starting point of the ring and the head node head is k - m, that is, if you advance k - m steps from head, you can reach the starting point of the ring.

Coincidentally, if you continue to advance k - m steps from the meeting point, you also happen to reach the starting point of the ring.

So, as long as we point either of the fast or slow pointers back to head, and then the two pointers move forward at the same speed, they will meet after k - m steps, and the place where they meet is the starting point of the ring.

Find the middle point of the linked list.

Similar to the above idea, we can also make the fast pointer advance two steps at a time, and the slow pointer advance one step at a time. When the fast pointer reaches the end of the linked list, the slow pointer is in the middle of the linked list.

1
2
3
4
5
6
while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
//slow is in the middle
return slow;

When the length of the linked list is odd, slow happens to stop at the midpoint; if the length is even, the final position of slow is right-of-center:

An important function of finding points in a linked list is to merge and sort the linked list.

Recall the merging sort of arrays: find the midpoint index recursion divides the array into two parts, and finally merges two ordered arrays. For linked lists, merging two ordered linked lists is very simple, and the difficulty lies in binary.

But now you have learned to find the midpoint of the linked list, you can achieve the two points of the linked list. The specific content of merging and sorting is not specifically expanded in this article.

** 4. Find the k-th element from the bottom of the linked list **

Our idea is to use the fast and slow pointer, let the fast pointer take k steps first, and then the fast and slow pointers start to advance at the same speed. In this way, when the fast pointer reaches null at the end of the linked list, the position of the slow pointer is the k-th penultimate linked list node (for simplicity, assuming k does not exceed the length of the linked list):

1
2
3
4
5
6
7
8
9
10
ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

Left and right pointers

The left and right pointers in the array actually refer to two index values, usually initialized as left = 0, right = nums.length - 1.

** 1, binary search **

The previous “binary search” has a detailed explanation, here only write the simplest binary algorithm, designed to highlight its double pointer characteristics:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid]  target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

** 2, the sum of two numbers **

Let’s take a look at a LeetCode topic directly: https://leetcode-cn.com/problems/two-sum/

As long as the array is ordered, you should think of the double-pointer trick. The solution to this problem is somewhat similar to binary search. By adjusting left and right, you can adjust the size of sum:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum  target) {
            The required index for the topic starts from 1
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            Left ++; // make the sum bigger
        } else if (sum > target) {
            Right --; // make the sum smaller
        }
    }
    return new int[]{-1, -1};
}

** 3. Reverse array **

1
2
3
4
5
6
7
8
9
10
11
void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

** 4, sliding window algorithm **

This may be the highest state of the two-pointer technique. If you master this algorithm, you can solve a large class of substring matching problems, but the “sliding window” is slightly more complex than the above algorithms.

Example

Sum of three numbers:

https://leetcode-cn.com/problems/3sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var threeSum = function (nums) {
  nums.sort((a, b) => { return a - b })
  //Sort first before clamping left and right
  let res = []
  for (k = 0; k < nums.length; k++) {
    if (nums[k] > 0) break
    //If the current number is greater than 0, no loop is needed, because k is the smallest number, the smallest number is already greater than 0, and the sum of three numbers cannot be equal to 0.
    if (k > 0 && nums[k] = nums[k - 1]) continue
    //deduplicate
    let i = k + 1
    let j = nums.length - 1

    while (i < j) {
      //Pinch condition, if both boundaries are next to each other, there is no need to loop
      let sum = nums[k] + nums[i] + nums[j]
      if (sum = 0) {
        //push to the return array if the condition is met
        res.push([nums[k], nums[i], nums[j]])
        while (nums[i] = nums[++i]) { }
        while (nums[j] = nums[--j]) { }
        //deduplicate, equivalent to the following four sentences, after deduplicate, it also points to the one that is not repeated
        // while (nums[i] = nums[i + 1]) { i++ }
        // while (nums[j] = nums[j - 1]) { j-- }
        // i++
        // j--
      } else if (sum < 0) {
        //less than 0 means that the number on the left margin is small, move to the right, because the whole number is sorted
        //k > i + j, move i to the right to make i + j bigger
        // 
        i++
      } else {
        //left clip
        j--
      }
    }
  }
  return res
};

Link to the original text of the principle part:双指针技巧

Thanks to God Labuladong for his series of blogs, which really inspired me a lot.