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.
- 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
Learning video
Double pointers are often used in linear structures: linked lists, arrays
Examples
151. Reverse linked list
Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.
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:
if head is None or head.next is None:
return head
p1 = None
p2 = head
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
/**
* Definition for singly-linked list.
* 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* reverseList(ListNode* head) {
ListNode* p1 = nullptr;
ListNode* p2 = head;
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
Give you a linked list, delete the penultimate node of the linked list, and return the head 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:
p1 = head
p2 = head
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
return head
c + + implementation
/**
* Definition for singly-linked list.
* 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) {
ListNode* p1 = head;
ListNode* p2 = head;
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;
return head;
}
};
118. Circular linked list
Give you a head node of the linked list to judge whether there are links in the linked list.
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 Explanation: there are no links in the linked list.
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:
if not head or not head.next:
return False
p_slow = head
p_fast = head
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr)
{
return false;
}
ListNode* p_slow = head;
ListNode* p_fast = head;
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:
if not head or not head.next:
return head
pre_node = head
cur_node = head.next
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
return head
c + + implementation
Follow behind
/**
* Definition for singly-linked list.
* 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* deleteDuplicates(ListNode* head) {
if(head==nullptr || head->next==nullptr)
{
return head;
}
ListNode* cur = head;
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;
}
}
return head;
}
};
125. Sorting linked list
Give you the head node of the linked list. Please arrange it in ascending order and return the sorted linked list.
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:
if not head:
return head
if head.next == tail:
head.next = None # The disconnection is divided into nodes
return head
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
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
return dummyHead.next
return sortFunc(head, None)
c + + implementation
/**
* Definition for singly-linked list.
* 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* sortList(ListNode* head) {
return sortFunc(head, nullptr);
}
ListNode* sortFunc(ListNode* head, ListNode* tail)
{
if(head==nullptr)
{
return head;
}
if(head->next == tail)
{
head->next = nullptr; // to break off
return head;
}
ListNode* slow = head;
ListNode* fast = head;
while(fast != tail)
{
slow = slow->next;
fast = fast->next;
if(fast != tail)
{
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortFunc(head, mid), sortFunc(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2)
{
ListNode* dummyHead = new ListNode(0);
ListNode* tmp = dummyHead;
ListNode* tmp1 = head1;
ListNode* tmp2 = head2;
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;
}
return dummyHead->next;
}
};