The use of double Pointers in the algorithm sometimes feels very clever and solves a lot of problems. It is necessary to summarize. First, double Pointers are also a very broad concept, which is similar to I and J in traversal, but the difference is that the two Pointers move simultaneously, that is, there is no contribution complexity from O(N) to O(N*N), Therefore, it is highly respected by many algorithm bigwig, so it summarizes the common solution and routine of double pointer based on this.

1. Question type induction

Here, the question types are classified into three types as follows:

• Fast or slow pointer (two Pointers at different paces)

• Front and back two-ended Pointers (one at the head, one at the tail, drawn towards the middle)

• Fixed interval pointer (two Pointers spaced with I, I + k)

As I said, all three of these Pointers are done by traversing the array once, and their time complexity is less than or equal to O(N), and their space complexity is O(1) because there are only two Pointers.

2

2.1 Fast and slow pointer

Quite a classic question:

• Check if the list has a ring –

Move two hands out of step, one in front of the other, until the hands overlap

Leetcode.com/problems/li… , the code snippet is as follows:

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
          ListNode fast = head;
    while(slow ! =null&& fast ! =null) {
                 ListNode n = fast.next;
     fast = n == null ? null : n.next;
     if (slow == fast) {
         return true;
     }
                 slow = slow.next;
    }
    return false;
    }
Copy the code

• Find repeated complex numbers, find a repeated integer from the array: leetcode-cn.com/problems/fi…

The code is solved as follows:

public int findDuplicate(int[] nums) {
        // Think of it as a looping list, with fast and slow Pointers looping
        int index1 = 0;
        int index2 = 0;
        do
        {
            index1 = nums[index1];
            index2 = nums[index2];
            index2 = nums[index2];
            
        }while(nums[index1] ! = nums[index2]); index1 =0;
// Find the starting point at which the circle must meet at the beginning
        while(index1 ! = index2){ index1 = nums[index1]; index2 = nums[index2]; }return index1;
    }
Copy the code

2.2 Pointers to front and rear end points

• Binary search

Binary search is a typical before and after pointer question type, the code is as follows:

public static int binarySearch(int[] array, int targetElement) {
    int leftIndex = 0, rightIndex = array.length - 1, middleIndex = (leftIndex + rightIndex) / 2;
    
    while(leftIndex <= rightIndex) {
      int middleElement = array[middleIndex];
      if(targetElement < middleElement) {
        rightIndex = middleIndex - 1;
      }else if(targetElement > middleElement) {
        leftIndex = middleIndex + 1;
      }else {
        return middleIndex;
      }
      
      middleIndex = (leftIndex + rightIndex) / 2;
    }
    
    return -1;
  }

Copy the code

2.3 Fixed interval pointer

• Find the list midpoint leetcode-cn.com/problems/mi…

// The fast pointer Q takes 2 steps at a time, and the slow pointer P takes 1 step at a time.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while(q ! =null&& q.next ! =null) {
            q = q.next.next;
            p = p.next;
        }
        returnp; }}Copy the code

• Find the penultimate KTH element leetcode-cn.com/problems/li…

    // The fast pointer takes k steps, then the two Pointers move synchronously. When the fast pointer reaches the end, the slow pointer is the last KTH node in the linked list.

    public ListNode getKthFromEnd(ListNode head, int k) {
        
        ListNode frontNode = head, behindNode = head;
        while(frontNode ! =null && k > 0) {

            frontNode = frontNode.next;
            k--;
        }

        while(frontNode ! =null) {

            frontNode = frontNode.next;
            behindNode = behindNode.next;
        }

        return behindNode;
    }
Copy the code

3. Template summary

After looking at three codes, if you feel very simple, here are three code templates for double Pointers

// 1
l = 0
r = 0
whileI didn't go through itifGiven that l plus theta is equal to theta1
  r += 1
returnThe appropriate value//2. Left and right endpoint Pointers
l = 0
r = n - 1
while l < r
  ifTo find thereturnFind the value of theifCertain conditions1
    l += 1
  else ifCertain conditions2
    r -= 1
returnDid not find//3. Fixed spacing pointer
l = 0
r = k
whileThe custom logic is not iterated l +=1
  r += 1
returnThe appropriate valueCopy the code

Check your profile for more.