# Algorithm learning -- double pointer

2022-01-26 22:25:47 Yan Long

## Double pointer classification

• ` Speed pointer `
• ` Left and right pointer `

Speed pointer ： It mainly solves the problems related to linked lists , such as ： A typical way to judge whether a linked list contains a ring 、 The linked list is the second K Nodes, etc Left and right pointer ： It mainly solves the problem of array （ Or string ） Problems in ： such as ： Two points search

## Speed pointer

subject ： Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes . for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of

```ListNode* getKthFromEnd(ListNode* head, int k) {

for (int i = 0; i < k; i++) {
if (first == NULL) {
return NULL;
}
first = first->next;
}

while(first) {
later = later->next;
first = first->next;
}

return later;
}```

## Left and right pointer

subject ： Give a list of... In ascending order ` Orderly ` An array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts `tips: Unordered array summation , have access to map To do it `

```vector<int> twoSum(vector<int>& nums, int target) {

vector<int> res;

int left = 0;
int right = nums.size() - 1;
int sum = -1;
while (left < right) {
sum = nums[left] + nums[right];
if (sum == target) {
res.push_back(left);
res.push_back(right);
return res;
} else if (sum > target) {
right --;
} else if (sum < target) {
left ++;
}
}
return res;
}```

subject ： Given an array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts

``` public int[] twoSum(int[] nums, int target) {

HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
int currentFirst = nums[i];
int needSecond = target - currentFirst;
int nextIndex = -1;
if (map.containsKey(needSecond)) {
nextIndex = map.get(needSecond);
}
if (nextIndex >=0) {
return new int[]{i, nextIndex};
}
map.put(currentFirst, i);
}

throw new IllegalArgumentException("No two sum solution");
}```

https://en.cdmana.com/2022/01/202201262225444009.html