This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The basic concept

• Two-pointer techniques fall into two categories:
  • Fast and slow pointer:
    • Mainly solve problems in linked lists
    • Like checking whether a linked list contains a ring
  • Left and right Pointers:
    • The main solution is arrays or strings
    • Binary search for example

How fast a pointer

• Quick Pointers:
  • Initialize the head that points to the linked list
  • When moving forward, the fast pointer is preceded by the slow pointer
  • Can cleverly solve linked list related problems

Check whether the linked list contains rings

• Single linked list features:
  • Each node only knows the next node
  • So a pointer can’t tell if a linked list contains a ring
• If the list does not contain rings, the pointer will eventually encounter null. This means that the list has reached its end, indicating that the list does not contain rings

boolean hasCycle(ListNode head) {
	while(head ! = null) { head = head.next(); }return false;
}
Copy the code

• If there are rings in the list, the pointer is stuck in an infinite loop. There are no null Pointers as tail nodes in the ring array
• Fast and slow pointer algorithms using double Pointers:
  • A fast pointer and a slow pointer
  • If the list does not contain rings, the fast pointer fast will eventually encounter null, indicating that the list does not contain rings
  • If there are rings, the fast pointer will eventually pass the slow pointer by one circle and eventually meet the slow pointer, indicating that the linked list contains rings

boolean haCycle(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;
}
Copy the code

Returns the starting position of a ring in a linked list

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;
		}
	}
	slow = head;
	while(slow ! = fast) { fast = fast.next; slow = slow.next; }return slow;
}
Copy the code

• When fast and slow Pointers meet, let any of them point to the headhead.Then the fast and slow Pointers advance at the same speed, and the node where they meet again is the starting position of the ring:
  • At the first encounter, if the slow pointer took K steps, then the fast pointer fast must have taken 2k steps, that is, k more steps than the slow pointer, which is a multiple of the ring length
  • Assuming that the distance between the encounter point and the starting point of the ring is m, then the distance between the starting point of the ring and the head node is k-m, that is to say, if the head node advances k-m steps, the starting point of the ring can be reached
  • If you continue the first K-m steps from the encounter point, you also reach the beginning of the ring
  • Thus, simply repoint either of the fast or slow Pointers to head, and both Pointers proceed at the same speed, and the place where they meet is the start of the ring

Find the midpoint of the list

• You can make the fast pointer advance two steps at a time, the slow pointer advance one step at a time, and when the fast pointer reaches the end of the list, the slow pointer is in the middle of the list

while(fast.next ! = null && fast.next.next ! = null) { fast = fast.next.next; slow = slow.next; }return slow;
Copy the code

• When the length of the list is odd,slow stops exactly at the midpoint. If the length is even,slow ends up to the right of center
• Find the point in a list: merge sort a list
• The whole point of merge sort is binary:
  • Find the midpoint and recursively divide the array
  • Finally, merge two ordered arrays
  • For linked lists, the difficulty in merging two ordered lists is dichotomy

Find the penultimate KTH element of the list

• You can make the fast pointer fast take k steps first, and then the fast and slow Pointers start to advance at the same speed. In this way, when fast goes to null at the end of the linked list, the position of slow is the KTH from last of the linked list node, that is, the element at slow’s position is the KTH from last of the linked list

ListNode slow, fast;
slow = fast = head;
while (k --> 0) {
	fast = fast.next;
}
while(fast ! = null) { fast = fast.next; slow = slow.next; }return slow;
Copy the code

About pointer

• The left and right Pointers in an array actually refer to two index values
• Initialize left = 0, right = nums.length-1

Binary search

int BinarySearch(int[] nums, int target) {
	int left = 0;
	int right = nums.length - 1;
	
	while (left <= right) {
		int mid = left + (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;
}
Copy the code

The sum of two Numbers

• As long as the array is ordered, the two-pointer technique should be used
• Sum can be adjusted by adjusting left and right

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) {
			return new int[] {left + 1, right + 1};
		} else if (sum < target) {
			left++;
		} else if(sum > target) { right--; }}return new int[] {- 1.- 1};
}
Copy the code

Inversion array

void reverse(int[] nums) {
	int left = 0;
	int right = nums.length - 1;

	while (left < right) {
		// Convert the elements of the left and right Pointers of the array
		inttemp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; }}Copy the code

The sliding window

• The double pointer sliding window algorithm can solve the string matching problem
• Generally encountered string matching problems and substring related problems, the first thought of using the sliding window algorithm