The double pointer is the closest to the basic arithmetic idea of mathematics, and also the easiest idea to understand, its basic principle is “taking a difference”.

How fast a pointer

Define two Pointers, fast and slow. Fast is a bit faster than slow, fast is in front of slow, slow is behind. Use the distance difference between fast and slow to solve the problem.

1 The KTH element from the bottom of the list

Using the distance difference between the fast and slow Pointers, the fast and slow Pointers can be you in front of me, and the distance difference between us is d, and using this feature we can solve some mathematical problems.

Find the KTH element from the bottom of a singly linked list, link :{leetcode-cn.com/problems/li…

Because it’s a single linked list, you can only access it from the front to the back, not from the back to the front, which is kind of disgusting, so let’s think about it another way, the KTH from the bottom, which is the n-k positive number, let’s look at the code:

Public ListNode getKthFromEnd(ListNode head, int k) {// Count the length of the list, int length = 0; ListNode temp = head; while (temp ! = null) { temp = temp.next; length++; } temp = head; temp = head; temp = head; int index = length - k; while (index > 0) { temp = temp.next; index--; } return temp; }Copy the code

Code is very simple, pure use of mathematical methods to solve the problem, we take a total of steps n+(n-k), where n is the number of steps to find the length of the list, n-k is to find the positive number of steps n-k, so can be simplified, of course, we can use the fast pointer.

We define a fast pointer and a slow pointer, which both point to the head node. First move fast to the KTH positive position, at which time slow is still in the head node, and the distance difference between them is K. Then move fast and slow together until fast moves to the end, where fast is located at n. And the position of slow is n minus k, which is the positive number n minus k node, namely: the reciprocal of the k node, wonderful!

public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; While (k > 0) {fast = fast.next; k--; } // Then move fast and slow together until fast reaches the end, and then take n-k steps while (fast! = null) { fast = fast.next; slow = slow.next; } return slow;} return slow; }Copy the code

The code is very simple, we took k plus n minus k, so we took n steps, which is n minus K less than the first method, and that’s the beauty of the fast and slow pointer.

2 Whether the linked list has a loop

Take advantage of the difference in speed of the fast pointer, the fast pointer doesn’t necessarily mean that you’re in front of me, it could mean that you’re running faster than me, like you’re running twice as fast as me.

Given a linked list, determine whether there are rings in the list by linking {leetcode-cn.com/problems/li…

We can simply traverse rough use Hash table storage, if there is a ring, then there must be a node will be traversed twice, at this time the Hash table is detected with this element, can determine the list has a ring, but we have a better solution, that is how a pointer, we know that the earth is round, if a person runs fast, a man ran slowly, So the fast one will eventually meet the slow one. Similarly, we use the fast and slow pointer. The fast pointer moves two steps at a time, and the slow pointer moves one step at a time.

public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode fast = head; ListNode slow = head; // The loop terminates if the fast pointer does not move to the end, because if the fast pointer moves to the end, it must be acyclic while (fast! = null && fast.next ! = null) {// move the fast pointer two steps at a time fast = fast.next; // Move the cursor one step at a time. Slow = slow.next; // If we meet, we will return! if (fast == slow) return true; } // acyclic return false; }Copy the code

The time complexity of the code is n, and the space complexity is 1, which is the NB of the fast and slow pointer, because the fast and slow pointer only needs two Pointers, so its space complexity must be constant!

Pointer to the collision

So what we’re talking about is using the distance difference or the velocity difference, both from the same starting point, and we can also use the meeting point at both ends to solve some problems, such as binary search.

Binary search

Link {leetcode-cn.com/problems/bi…

We use left and right Pointers, and as long as the left and right Pointers don’t meet, we keep clamping to narrow the range until we find the target or the left and right Pointers meet.

public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; int mid; // while (left <= right) {// mid = (left + right) / 2; // Return directly! if (target == nums[mid]) return mid; Else if (target > nums[mid]) left = mid + 1; Else if (target < nums[mid]) right = mid - 1; } // Return -1; }Copy the code

Code is very simple, using left and right Pointers, constantly narrow the search scope, until find or left and right pointer collision so far!

Clamp force pointer

The terminating condition for a collision pointer is “collision”, sometimes we don’t need to collide, we just need to define a scope, but what the boundary of the scope is, we need to specify with a double pointer.

The container that holds the most water

{linkLeetcode-cn.com/problems/co…:

Our goal is simply to create the largest rectangle using the vertical bar and the X-axis. We define the left and right Pointers on both sides, moving and approximating to find the largest rectangle.

Public int maxArea(int[] height) {int left = 0, right = height.length - 1; int temp = 0; While (left < right) {int area = math.min (height[left], height[right]) * (right-left); // Int area = math.min (height[left], height[right]) * (right-left); Temp = math.max (temp, area); // if (height[left] <= height[right]) left++; // If (height[left] <= height[right]) left++; else right--; } return temp; }Copy the code

In this example, we keep moving the pointer to get the maximum size of the squeeze, and the condition to stop the squeeze is that the squeeze range is 0, which is right-left=0. Remember the squeeze rule for higher numbers?

E > 0, any positive integer | N1 N2 | – > e, because e is tend to be infinitely small positive integer, here the e expressed as zero, right for larger N1 and N2, left for the small, it is right – left > 0, namely left < right, That’s the terminating condition in our if. Double pointer is the most basic algorithm idea, we must master, and in daily coding rational use, in order to be handy.