### 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; } };