Series article guide
 Kiner algorithm brush topic (a) : linked list and linked list ideas
 Kiner algorithm: Recursion and stack (solve the expression evaluation problem)
 Kiner algorithm brush topic (3) : thread pool and task queue
 Do you really know binary trees?
 Do you really know binary trees?
 Kiner algorithm: Heap and Priority queue
 Kiner algorithm brush topic (five) : Heap (priority queue)
The open source project
All articles in this series will be collected and managed in GitHub. Welcome ISSUE and Star.
GitHub portal: Kiner algorithm
Basic concepts and linked list ideas

The basic concepts and structure of linked lists
In terms of the expression form in JS, linked list is actually an object structure with one attribute for storing data and one attribute for storing the address reference of the next node. Simple linked list structure is as follows:
function LinkNode(val, next=null) {
this.val = val;
this.next = next;
}
Blockchain, as we often hear about it, is essentially a linked list structure. The application scenarios of the linked list structure will be explained in detail below

List ideas
According to my personal understanding, the thought of linked list is not limited to a data structure like linked list, but has a property: every node has a unique structure or logic to which we can regard it as a structure with the thought of linked list. If this seems too abstract, we’ll take a look at LeetCode 202 and you’ll get a clearer picture
Linked lists and linked list ideas in our common framework
Vue
keepalive
It’s good for cache routing, so that changes can be quickly recovered after switching back, but since the cache is going to be stored in memory,keepalive
What is the way to prevent “memory explosion” caused by large amounts of data being stored in memory? The answer is to use data structures like linked lists. Simple description: Frequently cache data, how to ensure efficiency while avoiding memory card burst. Use:
LRUCACHE
LRU  CACHE
The cache elimination algorithm is described in more detail later
 Simple description: Frequently cache data, how to ensure efficiency while avoiding memory card burst. Use:
Vue3
, is also used when compiling singlefile componentsLRU_CACHE
, the specific code is inpackages/compilersfc/src/parse.ts
File, direct searchlrucache
You can see that. This is to prevent memory freezes during compilation, because you don’t know how many singlefile components your large project will have.
React
Fiber
The multiway linked list structure is used, includingchild
,sibing
,return
Three Pointers to the first child node, first sibling node, and parent nodeHooks
Using theThe queue
orThe list
Realization, therefore,Hooks
Not in theif... else
Or nested functions
Application scenarios of linked list ideas (structures)
 Dynamic allocation of disk space in the operating system
 Let’s say our hard drive has
100GB
And now I have to distribute20GB
How do we manage the remaining space on our hard drive? The answer is the linked list structure. For example: [20GB] [20GB] [60GB], if the space we apply for is the second 20GB space, so that our hard disk will appear two discontinuous fragments, so that we can use the structure of class linked list, the first 20GB and the back of the 60GB string together for management.
 Let’s say our hard drive has
 LRU cache elimination algorithm
 When the CPU for a resource, he will go to our memory to find, if found is used directly, without finding after read from the hard disk, and then to cache it up and the process, is also using the hash chain table structure (the hash chain table is in order to improve search efficiency), when there is a new resource is inserted, Insert data at the end of the list, then delete the head of the list and eliminate the oldest data
 The Fiber in the React
 React maintains our Fiber nodes using a structure similar to a 3way linked list
 Block chain
 Blockchain is essentially a linked list structure that connects data blocks one by one. It just uses mining to improve its complexity and security. In essence, it is still a linked list structure
 .
Gradual brush problem
141. Circular linked lists
Title description:
Given a linked list, determine whether there are rings in the list.
If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is 1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.
Returns true if there are rings in the list. Otherwise, return false.
Their thinking
In fact, there are many ways to determine whether a linked list has a ring, such as using a hash table to change space for time, can also use the method of fast or slow Pointers. Here, we will talk about a more efficient method of fast and slow Pointers.
First of all, we need to make it clear that if our list has rings, then when we iterate, it’s possible that we’ll keep going around in the rings, so. We can use this feature, define a slow pointer p (walk the one step at a time), then define a quick pointer q take two steps (every), joined the list have the ring, our quick Pointers and pointer next node is not null may occur, because had a ring is the last node will point start node. And, after a few more rounds of chase, our fast pointer will eventually catch up with our slow pointer and meet the slow pointer.
In this way, we can imagine this problem as we are familiar with the pursuit of a problem, translation: if the two of us play together run, I run 1 km per hour, you run 2 km per hour, if we are on a straight road games, then I will never meet with you, because you run faster than I, the distance between us would be more bigger. But if we’re running on a circuit, because you’re running twice as fast as ME, after a few more laps, you’re going to end up running a full lap ahead of me and meeting me.
Ok, the general idea is this, next to start the code:
Code implementation
/* * @lc app=leetcode.cn id=141 lang=typescript * * [141] circular linked list */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function hasCycle(head: ListNode  null) :boolean {
// If the header does not exist, there is no loop
// If there is only one node, it is impossible to form a ring
if(! head  ! head.next)return false;
// Define a fast pointer that takes one more step than a slow pointer
let slow = head, fast = head.next;
// If the fast and slow Pointers do not meet and the next node of the fast and fast Pointers exists, the loop continues
while(slow ! == fast && fast && fast.next) {// Slow the pointer one step at a time
slow = slow.next;
// Fast pointer takes two steps
fast = fast.next.next;
}
// If the speed horse pointer meets after the lap, there is a ring
return slow === fast;
};
// @lc code=end
Copy the code
142. Circular linked List II
Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.
To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is 1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.
Note: Modification of a given linked list is not allowed.
Their thinking
We have already seen how to determine if a linked list has a ring, but this is a step further. Let’s find out where the ring starts.
So, if this list has rings. We assume that the head of the linked list node list head distance ring is a m, the starting point of the distance, we define a fast (q) a slow (p) two Pointers, assume our slow pointer p walked into the starting point of the ring, then slowly pointer distance head node is a, because his speed is slow and fast pointer q pointer twice, so he walked to the position of the 2 a. So, next, let’s think about, how far does the fast pointer Q have to go to make one more lap than the slow pointer? Let’s call this distance x for the moment, because the fast pointer doesn’t take a step away from the slow pointer, so to catch up with the slow pointer, you must have gone a + x more steps. Then, we can get a formula like this: the length of the ring n = a + x, then the fast pointer to the start of the ring to travel the distance is actually a + xx, that is, a. Ok, in this step, we already know, to go a step to find the starting point, we can find that meeting point to the starting point of the distance = head node to the starting point of the distance, so, we can make slow pointer end node place, then speed pointer together go forward step by step, know how Pointers to meet again, in this way, we found the starting point of the ring.
The above description may be a bit abstract, but let’s look at the implementation code:
Code implementation
/* * @lc app=leetcode.cn id=142 lang=typescript * * [142] ring linked list II */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function detectCycle(head: ListNode  null) :ListNode  null {
if(! head)return head;
// If the list has only one node, there can be no rings
if(! head.next)return null;
let p = head, q = head;
// First, the array executes a loop
do {
p = p.next;// The slow pointer moves one step at a time, assuming length: a
q = q.next.next;// The fast pointer takes two steps at a time, assuming a length of 2a
} while(p ! == q && q && q.next)// The loop is broken if the fast and slow Pointers meet or if the next node of the fast and fast Pointers is null
// If the next node of the fast pointer is null, the list is not looped
if(q === null  q.next === null) return null;
// Return the slow pointer to the starting position
p = head;
// Then let the slow pointer go backwards from the starting point, and the fast pointer go backwards from the meeting point, until their meeting point is the starting point of the ring
// The fast pointer is at 2a, and the fast pointer is at a+x from the start of the ring
// Suppose the encounter point is x away from the starting point of the ring. Since the fast Pointers take one more step each time than the slow Pointers, when do the fast and slow Pointers meet
// That is, the fast pointer takes one step away from the slow pointer each time, and when x steps are taken, the fast and slow Pointers meet.
// So, from the point of encounter, the fast pointer also needs to take: a+xx=a step to reach the starting point
// Therefore, we use the fast and slow Pointers to work our way down from the encounter point and the head point, knowing that the encounter point is where our loop starts
while(p ! == q) { p = p.next; q = q.next; }return q;
}
// @lc code=end
Copy the code
202. Happiness number (embodiment of linked list idea)
Write an algorithm to determine whether a number n is a happy number.
Happiness number is defined as:
For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions. And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1. If you can change it to 1, then that number is happiness. Return true if n is the happy number; If not, return false.
Their thinking
This first question seems to have nothing to do with linked lists, but, in fact, the beginning of this problem is an embodiment of our idea of linked lists.
We’ve already said that a linked list is a data structure that has a unique pointer, but if we look at the stem of the problem, we can see that the happiness number is a statement that satisfies the unique pointer of the list:
# Enter the number 191 9 * * * * 2 + 2 = 82  > 8 * * 2 + 2 * 2 = 68  > 6 * * 2 + 8 * * 1 * * 2 + 2 = 100  > 0 0 * * * * 2 + 2  > 1Copy the code
It can be seen from the above structure that 82>68>100>1 have unique directivity, so we can use the idea of linked list to solve this problem.
So, where do we start? If a number is not a happy number, then it will form a linked list with a ring. If it is a happy number, then its last node only points to 1. Will it be easy to think about the problem in this way?
So, let’s see how the code works:
Code implementation
/* * @lc app=leetcode.cn id=202 lang=typescript * * [202
// @lc code=start
function isHappy(n: number) :boolean {
let p = n, q = n;
do {
// The slow pointer performs an operation
p = getNext(p);
// The fast pointer performs two operations
q = getNext(getNext(q));
} while(p ! == q && q ! = =1) // Enter the loop if the fast and slow Pointers do not meet and the fast Pointers are not 1
// After the loop ends, if the fast pointer is 1, it is the happy number
return q === 1;
};
function getNext(x: number) :number {
let res = 0;
while(x) {
// Get the sum of squares of each digit
res += (x%10) * *2;
// After the sum of squares, divide the original number by ten before entering the next operation logic
x = ~~(x / 10);
}
return res;
}
// @lc code=end
Copy the code
206. Reverse linked lists
Reverse a single linked list.
Example:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL advanced: you can reverse iterative or recursive list. Can you solve the problem in two ways?
Their thinking
We want to reverse a linked list, which means that the next pointer to each node points to the previous node
Code implementation
/* * @lc app=leetcode.cn id=206 lang=typescript * * [206] reverse linked list */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function reverseList(head: ListNode  null) :ListNode  null {
// Solution 1: use JS deconstruction assignment features to achieve
// let pre = null, p = head;
// while(p) {
// [p.next, pre, p] = [pre, p, p.next];
// };
// return pre;
/ / the recursive method
if(! head  ! head.next)return head;
let tail = head.next, p = reverseList(head.next);
head.next = tail.next;
tail.next = head;
return p;
};
// @lc code=end
Copy the code
92. Reverse linked list II
Inverts the linked list from position m to n. Use a scan to complete the inversion.
Description: 1 ≤ M ≤ N ≤ The length of the linked list.
Example:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL, m = 2, n = 4 output: 1 – > > 43 – > 2 – > 5 – > NULL
Their thinking
This inversion list is actually on the basis of the previous problem, add a qualification, from which node to which node inversion. We can first move a pointer to the node to be reversed, and then reverse n nodes.
Code implementation
/* * @lc app=leetcode.cn id=92 lang=typescript * * [92] reverse linked list II */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
// class ListNode {
// val: number
// next: ListNode  null
// constructor(val? : number, next? : ListNode  null) {
// this.val = (val===undefined ? 0 : val)
// this.next = (next===undefined ? null : next)
/ /}
// }
function reverse(head: ListNode, n: number){
// When the counter reaches 1, the reverse is complete and the list head is returned
if(n === 1) return head;
// Define a tail pointer to the next node of the head node, and recursively reverse the list without reversing the counter suggestion once
let tail = head.next, p = reverse(head.next, n  1);
// After the inversion, the next node of the head node points to the next node of the tail node,
head.next = tail.next;
// The next node of the tail points to the head
tail.next = head;
return p;
}
function reverseBetween(head: ListNode  null, left: number, right: number) :ListNode  null {
if(! head  ! head.next)return head;
// Set the virtual header
let pre = new ListNode(1, head);
let p = pre, count = right  left +1;
// Move the pointer to the last node in the list to be flipped
// If left is 2, we move the pointer to 1, and then hang the reversed list on next at 1
// This is why you use left instead of left
while(left){
p = p.next;
}
// Reverse the target list
p.next = reverse(p.next, count);
return pre.next;
};
// @lc code=end
Copy the code
25. A group of K reverse linked lists
You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.
K is a positive integer whose value is less than or equal to the length of the list.
If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.
Advanced:
Can you design an algorithm that only uses constant extra space to solve this problem? You can’t just change the values inside the nodes, you need to actually swap nodes.
Their thinking
In fact, the principle is similar to the above two problems, but with more processing of boundary conditions
Code implementation
/* * @lc app=leetcode.cn id=25 lang=typescript * * [25] K flip linked lists */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
// Reverse n nodes
function __reverseN(head: ListNode, n: number) {
if(n === 1) return head;
let tail = head.next, p = __reverseN(head.next, n 1);
head.next = tail.next;
tail.next = head;
return p;
}
function reverseN(head: ListNode, n: number) {
let count = n, p = head;
while(n && p) p = p.next;
// Check if there are enough n nodes, if not, do not reverse
if(! p)return head;
// If enough, reverse count
return __reverseN(head, count);
}
function reverseKGroup(head: ListNode  null, k: number) :ListNode  null {
// hair is the sentinel node, still using the double pointer (fast or slow pointer)
let hair = new ListNode(1, head), p = hair, q = p.next;
// If the inverted node is still the same as the previous q node, the actual inverted operation has not been performed, indicating that there are less than n nodes, breaking the loop
while((p.next = reverseN(q, k))! ==q) {// hair > 1 > 2 > 3 > 4 > 5 > null
// hair > 3 > 2 > 1 > 4 > 5 > null
// From the example above, we can see that in the list of k nodes inverted, the next node of 1 is actually the cell to be inverted next time
// So, we just need to move p to q, i.e. move the pointer to 4, and then move Q to the next node of P, i.e. 5,
// Then proceed to the next judgment
p = q;
q = q.next;
}
return hair.next;
};
// @lc code=end
Copy the code
Swap linked lists in pairs
Given a linked list, swap adjacent nodes in pairs and return the swapped list.
You can’t just change the values inside a node, you need to actually swap nodes.
Their thinking
So this is a special case of k inverse linked lists, so if k===2, we can just use it
Code implementation
/* * @lc app=leetcode.cn id=24 lang=typescript * * [24] Switch nodes in the linked list in pairs */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function __reverseN(head: ListNode, n: number) {
if(n === 1) return head;
let tail = head.next, p = __reverseN(head.next, n  1);
head.next = tail.next;
tail.next = head;
return p;
}
function reverseN(head: ListNode, n: number=2) {
let p = head, count = n;
while(n && p) {
p = p.next;
}
if(! p)return head;
return __reverseN(head, count);
}
function swapPairs(head: ListNode  null) :ListNode  null {
let hair = new ListNode(1, head), p = hair, q = p.next;
while((p.next = reverseN(q)) ! == q){ p = q; q = q.next; }return hair.next;
};
// @lc code=end
Copy the code
61. Rotate linked lists
Given a linked list, rotate the list by moving each node of the list k positions to the right, where k is nonnegative.
Example 1:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: k = 2, 4 – > 5 – > 1 – > 2 – > 3 – > NULL explanation: spin to the right step 1:1 – > 5 – > 4 – > 2 – > 3 – > NULL spin to the right step 2: 4 – > 5 – > 1 – > 2 – > 3 – > NULL example 2:
Input: 0 – > 1 – > 2 – > NULL, k = 4 output: 1 – > 2 – > 0 – > NULL explanation: spin to the right step 1:1 – > 2 – > 0 – > NULL spin to the right step 2:1 – > 2 – > 0 – > NULL spin to the right step 3: 0>1>2>NULL Rotate 4 steps to the right: 2>0>1>NULL
Their thinking
To rotate the list by K nodes, we only need to connect the first and last of the list to form a ring, and then loop the total number of nodes in the list to the right K times, and then break the ring. Then the next node in the broken position is actually the head node of the new list
Code implementation
/* * @lc app=leetcode.cn id=61 lang=typescript * * [61] rotate linked list */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function rotateRight(head: ListNode  null, k: number) :ListNode  null {
if(! head)return head;
let n = 1, p = head;
// Move the pointer to the last node and record the total number of nodes
while(p.next){
p = p.next;
n++;
}
// Join the last point with the header to form a looped list
p.next = head;
// Since the circular list is equivalent no matter how many turns it makes, modulo k and n get a smaller k value to avoid meaningless movement
k %= n;
// Subtract k from the total length of the loop to get the actual number of right shifts
k = n  k;
// Move the list k bits to the right
while(k) {
p = p.next;
}
// execute the header to the next node of p
head = p.next;
/ / broken ring
p.next = null;
return head;
};
// @lc code=end
Copy the code
Delete the NTH node from the penultimate list
Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.
Their thinking
To delete the NTH node of the derivative, we need to have a pointer to the node before the NTH node of the derivative, and then make the next node of this node point to the next node of the NTH node of the derivative.
Code implementation
/* * @lc app=leetcode.cn id=19 lang=typescript * * [19] Delete the NTH node from the list */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function removeNthFromEnd(head: ListNode  null, n: number) :ListNode  null {
// Start with the slow pointer to the virtual header and the fast pointer to the real header
let hair = new ListNode(1, head),p = hair, q = head;
// Move the fast pointer back n steps
while(n && q){
q = q.next;
}
// Then move p and Q to the right together until Q stops at some point
while(q) {
p = p.next;
q = q.next;
}
// In this case, the node p points to is the previous node of the node to be deleted. In this case, the next node of P points to the next node of p to achieve the deletion operation
p.next = p.next.next;
return hair.next;
};
// @lc code=end
Copy the code
83. Delete duplicate elements from sorted linked lists
Given a sorted linked list, remove all duplicate elements such that each element appears only once.
Example 1:
Input: 1>1>2 Output: 1>2 Example 2
Input: 1>1>2>3>3 Output: 1>2>3
Their thinking
This problem is actually very simple, we just need to determine whether the value of the current node is the same as the value of the next node, if so, delete the next node, otherwise, the pointer of the current node moves right to continue traversal
Code implementation
/* * @lc app=leetcode.cn id=83 lang=typescript * * [83] Removes duplicate elements in sorted lists */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function deleteDuplicates(head: ListNode  null) :ListNode  null {
// if(! head) return head;
// let p = head;
// while(p){
// // keeps deleting the same node until the value of the current node is different from the value of the next node
// while(p && p.next && p.val===p.next.val) p.next = p.next.next;
// // encountered a different value, p node moved back
// p = p.next;
// }
// return head;
if(! head)return head;
let p = head;
while(p.next){
if(p.val === p.next.val) {
p.next = p.next.next;
} else{ p = p.next; }}return head;
};
// @lc code=end
Copy the code
Delete duplicate element II from sorted list
Given a sorted linked list, delete all nodes with duplicate numbers, leaving only those numbers that are not duplicated in the original list.
Example 1:
Input: 1>2>3>3>4>4>5 Output: 1>2>5 Example 2
Input: 1>1>1>2>3 Output: 2>3
Their thinking
Compared to the last problem, we’re going to have to use the sentinel node, because we’re probably going to use the end node, and everything else is going to start the same way
Code implementation
/* * @lc app=leetcode.cn id=82 lang=typescript * * [82] Delete duplicate elements in sorted lists II */
// @lc code=start
/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val? : number, next? : ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
function deleteDuplicates(head: ListNode  null) :ListNode  null {
let hair = new ListNode(1, head), p = hair, q;
while(p.next) {
If the real header exists and its value is equal to the real header
if(p.next.next && p.next.val === p.next.next.val) {
// Use another node to actually find the first node whose value is different from the real header
q = p.next.next;
while(q && q.val===p.next.val) q = q.next;
// The next node of the p node points to the found q node
p.next = q;
} else {
// The node moves backp = p.next; }}return hair.next;
};
// @lc code=end
Copy the code
 This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign