### 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:

​ 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

#### Vue

• `keep-alive`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,`keep-alive`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:`LRU-CACHE`
• `LRU - CACHE`The cache elimination algorithm is described in more detail later
• `Vue3`, is also used when compiling single-file components`LRU_CACHE`, the specific code is in`packages/compiler-sfc/src/parse.ts`File, direct search`lru-cache`You can see that. This is to prevent memory freezes during compilation, because you don’t know how many single-file components your large project will have.

#### React

• `Fiber`The multiway linked list structure is used, including`child`,`sibing`,`return`Three Pointers to the first child node, first sibling node, and parent node
• `Hooks`Using the`The queue`or`The list`Realization, therefore,`Hooks`Not in the`if... 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 distribute`20GB`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.
• 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 3-way 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
• .

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 singly-linked 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
// Define a fast pointer that takes one more step than a slow pointer
// 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 + x-x, 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 singly-linked 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 the list has only one node, there can be no rings

// 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

// 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+x-x=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``````

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 singly-linked 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

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 – > > 4-3 – > 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 singly-linked 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)
/ /}
// }

// When the counter reaches 1, the reverse is complete and the list head is returned
// Define a tail pointer to the next node of the head node, and recursively reverse the list without reversing the counter suggestion once
// After the inversion, the next node of the head node points to the next node of the tail node,
// The next node of the tail points to the head
return p;
}

function reverseBetween(head: ListNode | null, left: number, right: number) :ListNode | null {
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

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.

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 singly-linked 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) {
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 enough, reverse 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 singly-linked 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) {
return p;
}

function reverseN(head: ListNode, n: number=2) {
let p = head, count = n;
while(--n && p) {
p = p.next;
}
}

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``````

Given a linked list, rotate the list by moving each node of the list k positions to the right, where k is non-negative.

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 singly-linked 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 {

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
// 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
/ / broken ring
p.next = null;

};
// @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 singly-linked 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 {
// 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 singly-linked 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 {
// 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;
// }
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 singly-linked 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``````