preface
In the previous article, a single linked list has been completely implemented from the bottom of the data structure, and also rely on the linked list such a data structure to achieve the stack and queue, in the implementation of queue on the linked list made some improvements. Recursion is not only used in this structure tree can also use the structure in the linked list, the list itself with recursive structure properties of natural, just list is too simple, it is a linear structure, so you can use a recursive way, such as using the cycle approach can be very easy to solve the problems of the linked list, starting from the list to lay a foundation of recursion, It is very beneficial to learn more about tree structure including a deeper understanding of recursive algorithms.
It’s the same old saying: 20% can be mastered by reading articles, 80% can be mastered by coding, thinking and drawing. Source warehouse
Don’t be a perfectionist. Control the “degree”.
Too much pursuit of perfection will push yourself too tight, can produce various anxious state of mind, finally even doubt yourself, consider, don’t stop, mastering the degree, there is no you to put those you think completely got the control, and then became an expert at one area, on the contrary once you have very strong disgust, That means you’re going to give up or you’ve given up, and even though you wanted it to be 100, it’s zero because you gave it up.
Learn to act on your own goals. Don’t stray from your goals while studying. Prioritize. Difficult things, you can slowly look back. That will be more promising, more can improve their harvest.
Linked lists and recursion
Learn recursion with lists on LeetCode, submit lists on LeetCode, and a few other things to pay attention to, and at the same time solve lists on LeetCode, the idea is different in some ways from the previous custom lists, The key difference here is that in some cases these programs are node-centric rather than wrapped as a whole list class.
Problem no. 203 in LeectCode: Delete an element in a linked list
Find the node before this node in the list, but there is no previous node for the head node, so use special handling or virtual head nodes to unify the operation.
For better testing, I’ve created a custom method that converts an array to a linked list. The first node of the list is the one you created, and the value of this node is the first value of the array. The other nodes are associated by next of the first node, corresponding to each value in the array.
Code and test cases
(class: ListNode, class: Solution,class: Solution2, class: Main)
ListNode
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
// Convert an array object to a linked list and append it to the current node
appendToLinkedListNode(array) {
let head = null;
if (this.val === null) {
// Add header
head = this;
head.val = array[0];
head.next = null;
} else {
/ / plug-in
head = new ListNode(array[0]);
head.next = this.next;
this.next = head;
}
// How to add nodes: header, tail, middle
// How to add nodes to the tail
for (var i = 1; i < array.length; i++) {
head.next = newListNode(array[i]); head = head.next; }}// Outputs the information in the linked list
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `ListNode: \n`;
arrInfo += `data = front [`;
let node = this;
while(node.next ! = =null) {
arrInfo += `${node.val}- > `;
node = node.next;
}
arrInfo += `${node.val}- > `;
arrInfo += 'NULL] tail';
// Display it on the page
document.body.innerHTML += `${arrInfo}<br /><br /> `;
returnarrInfo; }}Copy the codeSolution
class Solution {
// leetcode 203. Remove the list element
removeElements(head, val) {
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
var removeElements = function(head, val) {
// Special handling for the head step
while(head ! = =null && head.val === val) {
head = head.next;
}
// Return a null header
if (head === null) {
return null;
}
// Head is not null and head.val is not null
// Start with the next node of head.
let prev = head;
while(prev.next ! = =null) {
if (prev.next.val === val) {
let delNode = prev.next;
prev.next = delNode.next;
delNode = null;
} else{ prev = prev.next; }}return head;
};
}
Copy the codeSolution2
class Solution {
// leetcode 203. Remove the list element
removeElements(head, val) {
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
var removeElements = function(head, val) {
if (head === null) {
return null;
}
let dummyHead = new ListNode(0);
dummyHead.next = head;
let cur = dummyHead;
while(cur.next ! = =null) {
if (cur.next.val === val) {
cur.next = cur.next.next;
} else{ cur = cur.next; }}return dummyHead.next;
};
returnremoveElements(head, val); }}Copy the codeMain
class Main {
constructor() {
this.alterLine('Leetcode 203. Remove all nodes of the specified element');
let s = new Solution();
let arr = [1.2.3.5.1.2.1.3.5.3.5.6.3.1.5.1.3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
console.log(node.toString());
let result = s.removeElements(node, 1);
console.log(result.toString());
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}window.onload = function() {
// Execute main function
new Main();
};
Copy the coderecursive
Recursion is an extremely important mechanism to build logic, especially in the world of computers for advanced sorting algorithms usually need to use recursion, for computer science to master recursion is extremely important, even can say that the gap between the primary level and the advanced level of the key watershed. Recursion can do fractal graphics rendering, various advanced sorting algorithm visualization.
The essence of recursion is to take an original problem and turn it into a much smaller problem, the same problem, which is to reduce the size of the problem gradually, to a certain point, usually in recursion, when it’s too small to be small, it’s easy to solve the problem, and then the whole problem can be solved.
Use recursion examples
Array summation: Find the sum of n elements in an array
The Sum (arr) n – [0… 1] = arr [0] + Sum (arr [1]… n – 1) for the first time, the Sum (arr [1]… n – 1) = arr [1] + Sum (arr [2]… n – 1) for the second time,… Several times the Sum (arr) [n – 1… n – 1] = arr [n – 1) + Sum (arr []) for the last time. Every time is slowly smaller will be the same question which evolved into the basic problem, the most fundamental problem is solved, and then according to some logic before, so as to solve the problem, is just like a big problem, if he can be decomposed into thousands of small problems, all of the same character, and then to these small problem in the form of recursive processing, so that would be easier. If (arr. Length == cur) {return 0; } arr[cur] + sum(arr, cur+1); You’re constructing the answer to the original question. Sum (arr, cur+1); It’s the constant transformation of the original problem into smaller problems, the solution of many small problems added together, to build the answer to the original problem.
class Calc {
constructor() {}
// Recursive summation
sum(array, cur = 0) {
// Solve the basic problem
if (cur === array.length) {
return 0;
}
// Return to thought
// Break the original problem into smaller problems of the same nature
// Build the answer to the original question from the answers to many small questions
return array[cur] + this.sum(array, cur + 1);
}
// Summation of tail recursion
tailSum(array, cur = 0, result = 0) {
// Solve the basic problem
if (cur === array.length) {
return result; // The sum above is not the same
}
// Reduction idea: decompose the original problem into small problems with the same nature, and use the solution of the small problem to construct the solution of the original problem.
// Reduce or reuse program calls to the system stack: perform operations once and then execute subfunctions.
return this.tailSum(array, cur + 1, result + array[cur]); }}class Main {
constructor() {
this.alterLine(Recursive summation);
let calc = new Calc();
let arr = [1.2.3.4];
let arrInfo = ` [`;
for (var i = 0; i < arr.length - 1; i++) {
arrInfo += `${arr[i]}, `;
}
arrInfo += `${arr[arr.length - 1]}`;
arrInfo += `] `;
document.body.innerHTML += `${arrInfo}<br /><br />`;
this.show(calc.sum(arr));
this.show(calc.tailSum(arr));
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}window.onload = function() {
// Execute main function
new Main();
};
Copy the codesummary
For a complex recursive algorithm, this logic may be very complex, although the transformation problem is a difficult point, in fact, it is not so difficult, but many in the writing of logic to their own dizzy, the function itself call their own, do not have to be too tangled inside the program execution mechanism.
When writing a recursive function, it is important to pay attention to the semantics of the recursive function itself. For example, the sum function above is used to calculate the sum of all the numbers in an array from the beginning of the index cur to the last position. This is the “macro” semantics of this recursive function. When it comes to transformation logic you have to get rid of the idea that this is a recursive algorithm, that a recursive function is itself a function, and each function is actually doing a function. If you call function B from function A you don’t get dizzy, but if you call function A from function A, which is A recursive function you might get dizzy, it’s essentially the same as calling function B from function A.
You can when a child is this logic, the logic inside need to pass two parameters, it do is to seek the starting index cur in the array to the last position between the sum of all Numbers, you only use this function, as to whether the current function or functions don’t need to care about, is actually so simple a thing.
When writing recursive algorithm, sometimes don’t need you special micro trapped into recursive calls to what was entangled with the recursive call, you can directly use the recursive functions as a child function, this function can perform specific functions, and you want to do is to use this function to build your own logic, To solve this problem at the top.
Pay attention to the macro semantics of recursive functions. Think of the recursive function you are calling as a subfunction or a sublogic or a subprocedure, and then think of the subprocedure that will help you solve this problem. It takes a lot of practice to master it.
Natural recursive structural properties of linked lists, answer leectCode 203
class Solution {
// leetcode 203. Remove the list element
removeElements(head, val) {
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
// There are three ways to solve recursively
var removeElements = function(head, val) {
// Solve the basic problem
if (head === null) {
return null;
}
// The first solution
// let node = removeElements(head.next, val);
// if (head.val === val) {
// head = node;
// } else {
// head.next = node;
/ /}
// return head;
// The second solution
// if (head.val === val) {
// head = removeElements(head.next, val);
// } else {
// head.next = removeElements(head.next, val);
// }
// return head;
// The third way
head.next = removeElements(head.next, val);
if (head.val === val) {
return head.next;
} else {
returnhead; }};// The tail recursion mode fails to that extent
// var removeElements = function(head, val, node = null) {
// if (head === null) {
// return node;
/ /}
// return removeElements(head.next, val , node = head);
// }
returnremoveElements(head, val); }}class Main {
constructor() {
this.alterLine('Leetcode 203. Delete all nodes of the specified element (recursive)');
let s = new Solution();
let arr = [1.2.3.5.1.2.1.3.5.3.5.6.3.1.5.1.3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
console.log(node.toString());
let result = s.removeElements(node, 2);
console.log(result.toString());
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}window.onload = function() {
// Execute main function
new Main();
};
Copy the codeThe mechanism of recursion and the “micro” interpretation of recursion
Although write a recursive function with a recursive algorithm to pay attention to the macro semantic recursive algorithm, but standing on a higher level to think about what is the function of the function itself, may help you to complete the whole better recursive logic, but on the other hand from a recursive function thought, recursive functions what works, what is its internal mechanism, So the mechanics of recursion also need to be understood.
By array sum and remove linked list node recursive implementation to specific to observe the operation mechanism of recursion, the application of stack in the said program invocation stack system, the location of the sub function call stack will pressure into a system, when the function call made, program will be found in the system stack last father function call son function of this position, In fact, there is no difference between the recursive call and the call of the child function and the child procedure, but the recursive call is still the function itself (calling itself, terminating the call itself according to certain conditions).
Recursive calls are indistinguishable from subroutine calls, just like the system stack of program calls. Father functions call the son, the son after function has been completed, it will return to the upper layer and continue to implement the parent function, not to perform the execution, but from before when the child function calls on to the location of the execution, if the function returns a value, then receive the can, after receiving continue to perform.
A0();
function A0 () {... A1(); . }function A1 () {... A2(); . }function A2 () {... . . }Copy the codeRecursive calls have a cost
Function call + system stack space. For example, the system stack will record the information of these function calls, such as the current function execution where, the current local variables are what a state, and then push it into the system stack. Including the function call itself and finding the location of the new function at the bottom of the computer is time consuming. Recursive calls consume stack space. If a recursive function does not handle the most basic case, the recursion will continue and will not terminate normally. The final result will be an exception because the stack is full and there is not enough space. In a linear call, when you recurse 100 million times, the system is still full because it stores too much information about the state of the function call.
It’s actually much easier to write logic recursively, and you can’t see this in linear structures, because linear structures are very nice. You can solve all linear problems by writing loops, but once you get into nonlinear structures like trees and graphs, many problems are actually much easier to solve recursively.
Recursive resolution of array summation
The function
// Calculate the sum of all the numbers in arr[cur...n].
sum (arr, cur = 0) {
// This is the place to solve the basic problem
// Usually for recursive algorithms,
// The basic problem is extremely simple,
// All of these are in the same form
// Because the basic problem is too mundane
// You can see the answer at a glance
if (arr.length === cur) {
return 0;
}
// This is the core part of the recursive algorithm F
// The process of turning the original problem into a smaller one
// This process is difficult,
// This translates into a smaller problem rather than a simple answer to a smaller problem,
// Instead, build the answer to the original question from the answer to the smaller question,
// The construction here is an addition process.
return arr[cur] + this.sum(arr, cur + 1);
}
Copy the codeAnalytic function
Recursive function calls are essentially function calls, but the function called is itself.
// Calculate the sum of all the numbers in arr[cur...n].
sum (arr, cur = 0) {
if (arr.length === cur) {
return 0;
}
temp = sum(arr, cur + 1);
result = arr[cur] + temp;
return result;
}
Copy the codeThe sum function is called in a new sum function. All the variables in the original sum function remain unchanged. When the new sum function is finished, it will return to the original sum function and continue to execute the rest of the logic.
// Calculate the sum of all the numbers in arr[cur...n].
/ / code 001
// use arr = [6, 10]
Sum (arr, 0)
sum (arr, cur = 0) {
if (cur == n) return 0; // n is the array length: 2
temp = sum(arr, cur + 1); / / cur is 0
result = arr[cur] + temp;
return result;
}
/ / code 002
// Sum (arr, cur + 1)
Sum (arr, 1)
sum (arr, cur = 0) {
if (cur == n) return 0; // n is the array length: 2
temp = sum(arr, cur + 1); / / cur to 1
result = arr[cur] + temp;
return result;
}
/ / code 003
// Sum (arr, cur + 1)
// sum(arr, 2)
sum (arr, cur = 0) {
// n is the length of the array: 2, cur is also: 2
// So the sum function stops at this point
if (cur == n) return 0;
temp = sum(arr, cur + 1); / / cur to 2
result = arr[cur] + temp;
return result;
}
// the sum function 003 returns 0.
//
// Then the sum function 002 above
// temp = sum(arr, cur + 1);
// Then execute the following logic where temp is interrupted when sum (002) is retrieved:
// result = arr[cur] + temp,
// temp = 0, cur = 1, arr[1] = 10,
// The sum function 002 completes, and returns 10.
//
// The sum function with the code 001
// temp = sum(arr, cur + 1)
// Then proceed to the logical position where temp is interrupted when sum (001) gets the value.
// result = arr[cur] + temp,
// temp = 10, cur = 0, arr[0] = 6,
// Sum (001) returns 16.
//
Sum (001) is not called by sum (00x).
// So the sum is 16.
Copy the codeDebug recursive function ideas
If you don’t understand how recursive functions work, don’t think about recursive functions. In many cases, you will get confused. You can use a very small test data set and throw it directly into this function. Step by step to see what the program calculates after each step is executed. It’s usually a way to get a clearer understanding of how the program works. Computer science is an engineering, and engineering science, and engineering science is very theoretical and it has theoretical support behind it, but it’s very, very important to practice from an engineering perspective. A lot of times if you want to understand the theory behind it, it’s probably better not to think about the theory, but to actually do it and see how the process works.
Removes recursive resolution of linked list nodes
The function
var removeElements = function(head, val) {
if (head == null) {
return null;
}
head.next = removeElements(head.next, val);
if (head.val == val) {
return head.next;
} else {
returnhead; }};Copy the codeAnalytic function
After the call, the subprocedure calculates the result and then returns it to the upper layer step by step. Finally, the final result is obtained, and 6->7->8-> NULL is obtained after deleting 7. The actual deletion of the node takes place in Step 3. After using the corresponding solution to a smaller problem, the current call and organization logic are combined to organize the solution of the current problem, which is such a process.
// The operation is 001
var removeElements = function(head, val) {
/ / the head: 6-7-8 - > > > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Delete 7 from 6->7->8->null
// Call removeElments(head, 7);
// Perform step 1. The current node of head is 6.
Next = removeElements(head.next, 7),
// Select a node after the current node.
// But it can be done with a subprocedure call like removeElements(head.next, 7),
// Next of the current node, 7->8->null.
// Operation number 002
var removeElements = function(head, val) {
/ / the head: 7-8 - > > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Delete 7 from 7->8->null
// Call removeElements(head.next, 7);
// head. Next is assigned to the local variable head in the function,
RemoveElements (head, 7);
// Perform step 1. The current node of head is 7, not null, so null is not returned.
Next = removeElements(head.next, 7),
// Select a node after the current node.
// But it can be done with a subprocedure call like removeElements(head.next, 7),
// Next of the current node, 8->null.
// Operation number 003
var removeElements = function(head, val) {
/ / the head: 8 - > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Delete 7 from 8->null
// Call removeElements(head.next, 7);
// head. Next is assigned to the local variable head in the function,
RemoveElements (head, 7);
// Perform step 1. The current node of head is 7, not null, so null is not returned.
Next = removeElements(head.next, 7),
// Select a node after the current node.
// But it can be done with a subprocedure call like removeElements(head.next, 7),
// Next is the next node of the current node, null.
// Function number 004
var removeElements = function(head, val) {
/ / the head: null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Simulate a call to null to delete 7
// Call removeElements(head.next, 7);
// head. Next is assigned to the local variable head in the function,
RemoveElements (head, 7);
// Perform step 1. The current node of head is null.
// Operation number 003
var removeElements = function(head, val) {
/ / the head: 8 - > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Return to the upper layer of function 004,
// call 003 to step 2, head. Next receives null,
// Continue with step 3 of function 003 and check whether val of the current node is 7.
// It is clear that the current node in 003 has val 8, so return the current node 8->null.
// Operation number 002
var removeElements = function(head, val) {
/ / the head: 7-8 - > > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Go back to the previous layer of function 003,
Head. Next returns node 8->null,
// Continue with step 3 of function 002 to check whether val of the current node is 7,
// Next 8->null;
Head: 7->8->null; return the next node of the current node.
// This removes the current node and makes next of the parent node point to next of the current node.
// The operation is 001
var removeElements = function(head, val) {
/ / the head: 6-7-8 - > > > null
/ / step 1
if (head == null) return null;
/ / step 2
head.next = removeElements(head.next, val);
/ / step 3
return head.val == val ? head.next : head;
};
// Return to the previous layer of the operand (002)
// head. Next returns 8->null,
// Proceed to step 3 of function 001 and check whether val of the current node is 7.
// return the current node head: 6->8->null
// Head: 6->7->8->null
Next (head: 7->8->null);
// The current node is head: 6->8->null.
// All nodes with val = 7 in the linked list are removed.
Copy the codeDebugging of recursive algorithms
Animation can be used to show the underlying operation mechanism of recursive functions, and animation frame by frame can be used to show the specific execution process of recursive functions.
But when you’re actually debugging recursive functions
- It’s hard to draw that kind of detailed animation and it’s relatively time consuming,
- But you can also take an A4 piece of paper and look at it carefully,
- For example, draw a small test case execution process,
- This is very useful for understanding your program or finding bugs in your program,
- It’s very helpful
Debugging method by printing output, can be used to print out a clear way to see how the program is in the process of execution step by step to obtain the final result. Step tracing, which is the debugging functionality that comes with every IDE. It depends.
For recursive function has a very important concept, the depth of the recursion, and every function within his own will to call yourself, then you on behalf of each call, the recursion depth is more than 1, so in the specific output visualized the recursive function, the recursion depth is can help you understand the recursive process of a variable, Add a depth parameter to the original recursive function. Generate a recursive depth string based on this variable –, — the same recursion depth.
Most of the time to really understand an algorithm or understand a function, in fact there is no shortcut, definitely takes some time, if you don’t want to draw on the paper, then you have to use the code to draw out, namely to add a lot of auxiliary code in the code, this is to understand the program, or do exercise at ordinary times when don’t lazy, It might take four lines of code to solve the problem, but chances are you’ve written dozens or even hundreds of lines of code to finally understand the program so thoroughly that you can solve the problem in four lines of code.
Keep practicing how to write a recursive function to understand the recursive process.
Code sample
(class: ListNode, class: Solution)
ListNode
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
// Convert an array object to a linked list and append it to the current node
appendToLinkedListNode(array) {
let head = null;
if (this.val === null) {
// Add header
head = this;
head.val = array[0];
head.next = null;
} else {
/ / plug-in
head = new ListNode(array[0]);
head.next = this.next;
this.next = head;
}
// How to add nodes: header, tail, middle
// How to add nodes to the tail
for (var i = 1; i < array.length; i++) {
head.next = newListNode(array[i]); head = head.next; }}// Outputs the information in the linked list
// @Override toString 2018-10-21-jwl
// toString () {
// let arrInfo = `ListNode: \n`;
// arrInfo += `data = front [`;
// let node = this;
// while (node.next ! == null) {
// arrInfo += `${node.val}->`;
// node = node.next;
/ /}
// arrInfo += `${node.val}->`;
// arrInfo += "NULL] tail";
// // is displayed on the page
// document.body.innerHTML += `${arrInfo}
`;
// return arrInfo;
// }
toString() {
let arrInfo = `ListNode = `;
arrInfo += `front [`;
let node = this;
while(node.next ! = =null) {
arrInfo += `${node.val}- > `;
node = node.next;
}
arrInfo += `${node.val}- > `;
arrInfo += 'NULL] tail';
returnarrInfo; }}Copy the codeSolution
class Solution {
// leetcode 203. Remove the list element
removeElements(head, val) {
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
* @param {number} val
* @return {ListNode}* /
// Understand recursion in depth
var removeElements = function(head, val, depth = 0) {
// The first output starts calling the function
let depthString = generateDepathString(depth);
let info = depthString + 'Call: remove ' + val + ' in ' + head;
show(info);
if (head === null) {
// The second output solves the most basic problem
info = depthString + 'Return: + head;
show(info);
return null;
}
let result = removeElements(head.next, val, depth + 1);
// The third output breaks the original problem into smaller problems
info = depthString + 'After: remove' + val + ':' + result;
show(info);
let ret = null;
if (head.val === val) {
ret = result;
} else {
head.next = result;
ret = head;
}
// Output the fourth time to solve the small problem
info = depthString + 'Return: + ret;
show(info);
return ret;
};
// The helper function generates a recursive depth string
function generateDepathString(depth) {
let arrInfo = ` `;
for (var i = 0; i < depth; i++) {
arrInfo += `-- `; // -- denotes depth, -- denotes the same recursive depth
}
return arrInfo;
}
// Auxiliary functions output content to the page and console
function show(content) {
document.body.innerHTML += `${content}<br /><br />`;
console.log(content);
}
returnremoveElements(head, val); }}class Main {
constructor() {
this.alterLine('Leetcode 203. Delete all nodes of the specified element (recursive) debugging');
let s = new Solution();
let arr = [1.2.3];
let node = new ListNode(null);
node.appendToLinkedListNode(arr);
this.show(node);
s.removeElements(node, 2);
}
// Display the content on the page
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// Display the dividing line
alterLine(title) {
let line = ` -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --${title}-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- `;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`; }}Copy the codeconclusion
In terms of recursion, linked lists have a natural recursive structure, and almost all operations related to linked lists can be done recursively.
This exercise is very meaningful and can help you better understand recursion. Before, the addition, deletion, change and check of linked list were implemented in a circular way. Now, the addition, deletion and check of linked list can be implemented in a recursive way. You don’t need recursion to actually use linked lists, but doing this exercise will give you a better understanding of recursion.
Other topics related to linked lists are on Leetcode, linked lists: https://leetcode-cn.com/tag/linked-list/. Do not be perfectionist, do not try to solve all these problems at once, according to their own actual situation to make a plan, when they are at what level, what kind of problems to complete, but these problems will always be in Leetcode, slowly, little by little.
On the list of technical research, put forward by Stanford problem research, the article address: https://max.book118.com/html/2017/0902/131359982.shtm, all understand, that you fully understand the linked list.
Nonlinear data structure, such as the well-known binary search tree is a binary search tree dynamic data structure also depend on node articulated, only those nodes arranged in a line, but arranged in a tree, each node has not point to the next node next, but by refers to the right sub tree and left subtree two root nodes.
extension
Double linked list
For queues, we need to operate on both ends of the list. We run into problems when we operate on both ends of the list. Deleting elements at the end of the list is O(n) complexity, even if there is a tail variable at the end pointing to the end of the list. Actually there is a solution for this problem, the solution to this problem is double linked list, the so-called double linked list is in the list each node contains two Pointers pointer represents references, there is a variable next point to the next node in this node, a variable prev point to a node before this node, for double linked list, Once you have the tail node, it’s easy to remove the tail node, and the operation can be O(1) level, but the cost is that each node has two Pointers instead of one, which can be more complex to maintain.
class Node {
e; // Element
next; //Node
prev; //Node
}
Copy the codeCircular linked list
For circular linked list, you can also use the thinking of double linked list to achieve, but the head of the need to set up a virtual node, thus make the whole list form a ring, it is the most important is not pointing to the empty but points to the virtual head end node, can easily determine whether a certain node next node is the virtual head node, To determine if this node is a tail node. The advantage of a circular list is that it further unifies many operations. For example, to add an element to the end of a LinkedList, you only need to add an element before dummyHead, which is equivalent to adding an element to the end of the entire list. In fact, the circular list itself is very useful. It is the underlying implementation of the LinkedList class in strongly typed Java, essentially a circular list. More accurately, it is a circular bidirectional list, because each node has two Pointers.
Linked lists are also implemented using arrays
Because next only points to the next element, each location in the array stores not only that element, but an index that points to the next element. Each Node in the list looks like this. The Node class has an int next that points to the index of the next element. In some cases, such as when you know exactly how many elements you’re dealing with, it might be more convenient to use an array linked list.
class Node {
e; // Element
next; //int
}
Copy the code