# Algorithm: double pointer

### Double pointer

Double pointer is an idea or a skill, not a specific algorithm.
Specifically, we use two variables to dynamically store two nodes to facilitate some operations. Usually used in linear data structures.

Especially for the problems of linked list, it is often necessary to use two or more pointers to memorize the nodes on the linked list and complete some operations.

### Common double pointer mode

• Same speed pointer: two pointers on the linked list, one starts first, the other starts later and follows at the same speed.
• Find the inverse of the linked list: make the double pointers move forward synchronously through the temporary pointer
• Find the penultimate element of the linked list: first move one pointer forward by k steps, and then the two pointers together at the same speed
Move forward until the previous pointer reaches the end, and the subsequent pointer is the penultimate element
• Speed pointer: two pointers on the linked list start from the same node, and one pointer advances faster than the other pointer (faster than the other)
(e.g., twice the other pointer)
• Calculate the midpoint of the linked list: the fast and slow pointer starts from the first node. In each round of iteration, the fast pointer moves forward by two nodes, slow
The pointer moves forward one node. Finally, when the fast pointer reaches the end point, the slow pointer is just in the middle node
• Judge whether the linked list has a ring: the speed pointer starts from the beginning node. If there is a ring in the linked list, the two pointers will eventually be in the ring
Meet in
• Find the length of the link in the linked list: as long as one doesn't move after meeting, the other advances until meeting. Calculate how many steps you have taken.

### Learning video

Double pointers are often used in linear structures: linked lists, arrays

### Examples

Example:

```Input: head = [1,2,3,4,5]
Output:[5,4,3,2,1]
```

```Input: head = [1,2]
Output:[2,1]
```
```Input: head = []
Output:[]
```

Problem solving ideas:

• Method 1: traverse once, use the list to store the elements, then reverse, and traverse again to string the elements
• Method 2: pass through pointer method. After two pointers are one before the other, use the intermediate variable to save the next node, and then move the assignment

python implementation

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:

p1 = None
while p2:  # Just draw a picture
tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
return p1  # p1 is in front of p2, and p2 is already the end None
```

c + + implementation

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* p1 = nullptr;
while(p2 != nullptr)
{
ListNode* tmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmp;
}
return p1;
}
};
```

#### 18. Delete the penultimate node of the linked list

Example 1:

```Input: head = [1,2,3,4,5], n = 2
Output:[1,2,3,5]
```
```Input: head = [1], n = 1
Output:[]
```
```Input: head = [1,2], n = 1
Output:[1]
```

Problem solving ideas:

• Method 1: traverse once, save the val of each node in the linked list, turn it into a list, delete the value of the penultimate node, and then traverse again for concatenation
• Method 2: the fast and slow pointers, one does not move first, the other moves forward n steps, and then the two move together until the first pointer reaches the end, then the slow pointer reaches the nth-1st element at the end, and then set the element x.next = x.next next

python implementation

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

for i in range(n):  # Go n steps first
p2 = p2.next

if not p2:  # If the node has reached the end, it should be deleted
return p1.next

while p2.next:   # This is P2 Next, you need to step back
p1 = p1.next
p2 = p2.next

p1.next = p1.next.next
```

c + + implementation

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
while(n)
{
p2 = p2->next;
n--;
}

if(p2==nullptr)
{
return p1->next;
}

while(p2->next)
{
p1 = p1->next;
p2 = p2->next;
}

p1->next = p1->next->next;

}
};
```

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the links in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). Note: pos is not passed as a parameter. Just to identify the actual situation of the linked list.

Returns true if there are links in the linked list. Otherwise, false is returned.

Example 1:

```Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the second node.
```

Example 2:

```Input: head = [1,2], pos = 0
Output: true
Explanation: there is a ring in the linked list, and its tail is connected to the first node.
```

Example 3:

```Input: head = [1], pos = -1
Output: false
```

Problem solving ideas:

• Method 1: traverse and store the node in a hash table. The node is used as the key. If it is found that the node is already in the hash table during traversal, it indicates that there is a ring
• Method 2: use the speed pointer, one step at a time and two steps at a time. If the two overlap, it indicates that there is a loop.

python implementation

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
return False

while p_fast and p_fast.next:  # Add a judgment p to the condition_ Whether fast is a node and whether its next node is a node
p_slow = p_slow.next
p_fast = p_fast.next.next
if p_slow == p_fast:
return True
return False
```

c + + implementation

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
{
return false;
}

while(p_fast && p_fast->next)
{
p_slow = p_slow->next;
p_fast = p_fast->next->next;  // Take two steps
if(p_slow == p_fast)
{
return true;
}
}
return false;
}
};
```

#### 71. Delete duplicate elements in the sorting linked list

Given the head of a sorted linked list, delete all duplicate elements so that each element appears only once. Returns the sorted linked list.

Example 1:

```Input: head = [1,1,2]
Output:[1,2]
```

Example 2:

```Input: head = [1,1,2,3,3]
Output:[1,2,3]
```

Problem solving ideas:

• Method 1: use the idea of stack. If the later element is the same as the top element of the stack, skip the element and continue to traverse
• Method 2: Double pointers, one before and one after, and the following pointer is compared with the previous pointer element. If it is the same value, the latter pointer continues to go back. If not, the front pointer moves to the rear pointer position, and the rear pointer moves back one bit.

python implementation

Compared with the front

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:

while cur_node:  # To compare to the end, use cur here_ Node is not cur_node.next
if pre_node.val == cur_node.val:  # Compared with the previous node
pre_node.next = cur_node.next
cur_node = cur_node.next
else:
pre_node = cur_node
cur_node = cur_node.next
```

c + + implementation

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
{
}

while(cur->next != nullptr)
{
if(cur->val == cur->next->val)  // Compare with the following element. If the latter element is the same as the cur element, skip the latter element
{
cur->next = cur->next->next;
}
else  // If not, cur moves back one node
{
cur = cur->next;
}
}
}
};
```

Example 1:

```Input: head = [4,2,1,3]
Output:[1,2,3,4]
```

Example 2:

```Input: head = [-1,5,3,4,0]
Output:[-1,0,3,4,5]
```

Example 3:

```Input: head = []
Output:[]
```

Problem solving ideas:

• Method 1: traverse and save the list, sort the list, traverse again and string the elements
• Method 2: use the speed pointer to cut the linked list into two parts, use the recursive method to sort the sub linked list, and then use the way of merging the single linked list to connect them in series. The termination condition of recursive sorting is that the number of nodes in the linked list is less than or equal to, that is, when the linked list is empty or the linked list contains only one node, there is no need to split and sort the linked list

python implementation

```class Solution:
def sortList(self, head: ListNode) -> ListNode:
def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
head.next = None  # The disconnection is divided into nodes
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow

while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2

```

c + + implementation

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
}

{
{
}

{
head->next = nullptr;  // to break off
}

while(fast != tail)
{
slow = slow->next;
fast = fast->next;
if(fast != tail)
{
fast = fast->next;
}
}

ListNode* mid = slow;
}

{
while(tmp1!=nullptr && tmp2 != nullptr)
{
if(tmp1->val <= tmp2->val)
{
tmp->next = tmp1;
tmp1 = tmp1->next;
}
else
{
tmp->next = tmp2;
tmp2 = tmp2->next;
}

tmp = tmp->next;
}

if(tmp1 != nullptr)
{
tmp->next = tmp1;
}
else if(tmp2 != nullptr)
{
tmp->next = tmp2;
}