# LeetCode - double pointer

## 26. Delete new elements in the array

Given a sort array, you need to delete duplicate elements in place so that each element appears only once, returning the new length of the array after removal.

Do not use extra array space, you must modify the input array in place and do so with O(1) extra space.

Example 1:
Given array nums = [1,1,2],
The function should return a new length of 2, and the first two elements of the original array nums are modified to 1, 2.

Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
The function should return a new length of 5, and the first five elements of the original array nums are modified to 0, 1, 2, 3, 4.

```class Solution {
public int removeDuplicates(int[] nums) {
//i refers to the number to be reserved;
//j traversing the entire array
int i = 0;
for(int j = 1; j < nums.length; j++){
if(nums[i] != nums[j]){
i++;//Find the number you need to keep, move i back, make room
nums[i] = nums[j];
}
}
return i+1;
}
}
```

## 633. Sum of squares

Given a non negative integer c, you need to determine whether there are two integers a and b, so that a2 + b2 = c.

Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:
Input: 3
Output: False

```class Solution {
public boolean judgeSquareSum(int c) {
int i = 0;
int j = (int) Math.sqrt(c);//Square root
int target = 0;
//When the sum of squares of two numbers is equal to 2, both i and j are equal to 1, indicating that i can be equal to J
while(i<=j){
target = i*i+j*j;
if(target == c){
return true;
}else if(target < c){
i++;
}else{
j--;
}
}
return false;
}
}
```

## 88. Merge two ordered arrays

Given two ordered integer arrays nums1 and nums2, nums2 is merged into nums1, making num1 an ordered array.

Explain:
The number of elements to initialize nums1 and nums2 is m and n, respectively.
You can assume that nums1 has enough space (space size greater than or equal to m + n) to hold the elements in nums2.

Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

```class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//Merge sort
//Since the fill number is after nums1, it starts traversing from the back to the front
int i1 = m-1;//Point to the end of nums1
int i2 = n-1; //Point to the end of nums2
int index = m+n-1;//Point to the end of the merged array

while(i1>=0 && i2>= 0){
//If nums1 is large, fill nums1
if(nums1[i1] > nums2[i2]){
nums1[index--] = nums1[i1--];
}else{
nums1[index--] = nums2[i2--];
}

}
//If there is still an array not filled out;
//If it's nums1, don't worry, because it's supposed to be filled with nums1;
//If it's nums2, assign it all
while(i2>=0){
nums1[index--] = nums2[i2--];
}
}
}
```

## 141. Circular list

In order to represent the links in a given linked list, we use the integer pos to represent the position where the end of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: there is a link in the list with the tail connected to the second node. Idea: traverse. If null is encountered, it must not be a ring;
Traversal, if the previous duplicate node is encountered, it must be a ring.
Two solutions: fast and slow pointer; HashMap
Corresponding situation: fast and slow pointer, imagine that two athletes are running long distance on the playground, and will definitely meet at last.
HashMap think of athletes taking photos every few minutes of running. There must be two photos of repeated scenes at last

```/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
//Without nodes, a ring cannot be formed;
//There is only one node, and it can't form a ring

//Fast and slow pointer
//Think about running on the playground,
//If there is a ring, the fast pointer will run twice, and the slow pointer will run once, and they will meet
while(fast != null && fast.next != null){
//Now let the fast pointer go two steps
//Slow pointer one step
slow = slow.next;
fast = fast.next.next;
//If we meet, there is a ring
if(slow == fast){
return true;
}
}
return false;
}
}
```
```/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
//Thought: judge whether the link list has a ring or not;
//Find the entrance to the ring
public class Solution {
//First, carry out a self check on the linked list
return null;
}

//Define a fast pointer, a slow pointer, and judge whether there is a ring or not
//Two steps for fast pointer and one step for slow pointer
//There are a nodes in front of the ring list entry, b nodes in the ring, and a+b nodes in the chain list
//So when we meet, the fast pointer takes the s+nb step
//fast is twice the number of slow steps, so f = s+nb = 2s
//f = 2nb, s= nb, this is the number of steps taken by the two pointers at the first meeting
//At this time, we want to know that the circular entrance, s has already taken nb steps, so we just need to let s take step a again and stop,
//After walking through the list, he (s) comes out of the list port, which is the circular entrance
//You can find out where the ring entrance is
//We still use the method of double pointer. We define a pointer, start from the beginning, walk with step a of s, and they will meet again at the circular entrance
//Because they've gone through the chain together
boolean hascycle = false;
while(fast!=null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
hascycle = true;
break;
//break is to jump out of the loop, in this topic, is to jump out of the if statement;
//Continue is to jump out of this cycle, but the next cycle will continue
}
}
//Define the third pointer. The place where the third pointer and slow pointer meet is the entrance of the ring
if(hascycle){
while(slow != third){
slow = slow.next;
third = third.next;
}
return third;
}
return null;
}
}
```  Published 48 original articles, won praise 3, visited 2364

Added by Eddyon on Tue, 18 Feb 2020 10:39:39 +0200