preface

Most of the previous articles are written for girlfriend series, but there is no update for a period of time, on the one hand, spring recruitment to prepare to start, on the other hand, girlfriend is still preparing for the interview before the interview, after the review summary is very important.

A visit to HearLing’s profile page continuously shares the front-end body of knowledge.

It seems that the more to the New Year, some writing time is more up, now share with you how we prepare the algorithm this piece, just as the spring recruitment is about to open, the year before the final preparation, I hope to help you.

If this article is not authorized by the author, it is forbidden to reprint, if found the same, will be held responsible!

I originally planned to introduce it through an article, recommend my way and route of brushing questions, and get some feedback from my partners: it is better to be more detailed, zero-based, small white, and github access speed is also a problem, it may not be able to load pictures.

So, I’m going to split it up into several posts so that you can get a good idea of what Chocolate has done with his first post in Denver. It will be the Spring Festival soon, I hope to help you with your spring recruit. The content plan is as follows:

• 🐮 Write a beginner’s guide to Zero-based front-end algorithms, acmer with my girl brush 80+ stacks and Queues and linked Lists (this issue has been completed 🎉)
• 🐮 for a beginner’s guide to zero-based front-end algorithms, Acmer with his girlfriend brush 80+
• 🐮 write a beginner’s guide to zero-based front-end algorithms, acmer with girlfriend brush 80+
• 🐮 write a beginner’s guide to zero-based front-end algorithms, acmer with girlfriend brush 80+
• 🐮 to write a zero-based front-end algorithm introduction guide, Acmer with his girlfriend brush 80+ [dynamic programming DP chapter]
• 🐮 to write a zero-based front-end algorithm primer, acmer with girlfriend brush 80+【 Summary 】

How do you prepare the algorithm

First of all, I would like to introduce myself briefly. I played ACM in school (if not, forget it, because there are no cards of great value, iron cards, participation cards and certificates are a lot of them).

If you know ACM and have participated in the domestic front-end interview, it should not take a long time to brush the questions. If you have any idea about my ACM experience, I will consider releasing a video in STATION B.

Therefore, it may take 10-20 days to prepare the algorithm for the zero-based xiaobai, while the cycle may be longer for non-academic classes. So, now I’m going to share how I took my girlfriend to do this.

• The first point, clear algorithm it is not very difficult things, to understand the fact that things, perhaps you will like to do the topic, of course, for ACM big guy to do the topic is another matter, the main body of this article and the interview level shall prevail
• Second, the front end of the algorithm is relatively simple, I encountered in the spring and Autumn recruitment process are some common questions, such as search, greedy, simple dynamic programming, classical sorting algorithm, are based onleetcodeSome simple and medium difficulty, and these algorithms for the class, should have learned in school, such as algorithm analysis and design, data structure and algorithm courses, then have this basis, your brush time can be shortened
• Third, since said to want to brush the topic, how to brush, I was in the nuggets reference for several bosses, (at the end of the article is the reference point) everyone TuiJianFen project to brush, in here, I also am very recommend, here, I want to brush algorithm to reduce the number of point, introduction to show you, when you brush after the project, you will have the relevant thinking initiative to brush the topic, Rather than very passive to brush, it is also very convenient to sum up their own ~
• Other, can refer to the big guy’s article, here no longer repeat…

A mind map to make your path easier

To cut to the chase, first provide a mind map, so that knowledge from complex to simple.

To obtain hd PDF, please reply to [LeetCode] on wechat public account [Little Lion front end]. You can add penguin group [666151691].

This warehouse brush topic route reference SSH (give big guy point praise) warehouse address: github.com/sl1673495/l…

Thanks for the boss’s summary, I originally planned to punch in and learn there, but later I decided to build a new warehouse to punch in and learn.

Secondly, most of the code to solve the problems in this warehouse is my own code style, and the questions have been expanded, and will continue to update, why not star collection?

The warehouse is introduced

Warehouse address: github.com/Chocolate19…

This warehouse will use JavaScript throughout the language, is a pure front-end brush topic route, for the front-end brush topic no direction of small partners is simply good news. The problem solving codes will be recorded in the Issues of the warehouse and classified according to label. For example, if you want to see problems in the “recursion and backtracking” category, select the TAB and filter.

At the same time, small partners can submit their own solution code in Issues, 🤝 welcome Contributing, can stick to the coolest person! Give a ⭐️ if this project helped you!

Brush question route

Now let’s start the process. Give this article a thumbs up, take out your favorite keyboard, and go!

The following topic order is only personal and interview points to summarize the brush questions, you can mix according to their own ideas. Please refer to this warehouse for more questions

The stack

20. Valid brackets

20. Valid parenthesis portal

Answer key

It was discovered that the further back the left parentheses were, the first match was made, so the data structure stack was considered.

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
  // If the match is odd, it cannot be matched successfully
  if(s.length & 1) return false
  let stack = []
  for(let i=0; i<s.length; i++){if(s[i] === '(' || s[i] === '{' || s[i] === '[') stack.push(s[i])
    else if(s[i] === ') ' && stack[stack.length-1= = ='(') stack.pop()
    else if(s[i] === '} ' && stack[stack.length-1= = ='{') stack.pop()
    else if(s[i] === '] ' && stack[stack.length-1= = ='[') stack.pop()
    else return false
  }
  return! stack.length };Copy the code

946. Validate stack sequence

946. Verify stack sequence original problem portal

Topic describes

Given two sequences of pushed and popped, the values in each sequence are not repeated, returning true only if they may be the result of a sequence of push and pop operations on the originally empty stack; Otherwise, return false.

Example 1:

Input: pushed = [1.2.3.4.5], popped = [4.5.3.2.1] output:trueExplanation: We can execute the following order: push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Copy the code

Example 2:

Input: pushed = [1.2.3.4.5], popped = [4.3.5.1.2] output:falseExplanation:1Not in the2Before pop up.Copy the code

Tip:

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000Pushed is an array of popped.Copy the code

Their thinking

If the match is successful, both sides of the stack are removed from the stack. Finally, if the new stack is empty, this means that the sequence of the stack is reasonable, return true, otherwise return false

/ * * *@param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}* /
var validateStackSequences = function(pushed, popped) {
    // With a new stack
    let stack = []
    for(let cur of pushed){
        // Place the element on the stack
        stack.push(cur)
        // Compare with the elements out of the stack, if the match is out of the stack
        while(stack[stack.length-1] === popped[0] && stack.length){
            stack.pop()
            popped.shift()
        }
    }
    return! stack.length };Copy the code

921. Minimum additions to make parentheses valid

921. Add at least the original problem portal to make parentheses valid

Topic describes

Given a string S consisting of parentheses ‘(‘ and ‘)’, we need to add the minimum number of parentheses (‘ (‘ or ‘)’, anywhere) to make the resulting parenthesis string valid.

Formally, a parenthesis string is valid only if one of the following is true:

It is an empty string, or it can be written as AB (A concatenated with B), where both A and B are valid strings, or it can be written as (A), where A is A valid string. Given a parenthesis string, returns the minimum number of parentheses that must be added for the result string to be valid.

Example 1:

Input:"()"Output:1
Copy the code

Example 2:

Input:"((("Output:3
Copy the code

Example 3:

Input:"()"Output:0
Copy the code

Example 4:

Input:"())) (("Output:4
Copy the code

Tip:

S.length <= 1000S only contains'(' 和 ') 'Characters.Copy the code

Their thinking

Use a new stack and iterate over the current string, popping the top element if the current top element matches the current character parentheses, otherwise the number of parentheses needed is the number of remaining elements in the stack

/ * * *@param {string} S
 * @return {number}* /
var minAddToMakeValid = function(S) {
    // The length is 0
    if(! S.length)return 0
    let stack = []
    for(let i=0; i<S.length; i++){let ch = S[i]
        // If the current top of stack element matches the current character parentheses, the top of stack element is popped
        if(ch === ') ' && stack[stack.length-1= = ='(') stack.pop()
        else stack.push(ch)
    }
    // The number of remaining elements of the stack, i.e. the number of parentheses required
    return stack.length
};
Copy the code

901. Stock price span

901. Stock prices span the original problem portal

Topic describes

Write a StockSpanner class that collects daily quotes for certain stocks and returns the span of that stock’s price for that day.

The span of today’s stock price is defined as the maximum number of consecutive days (counting backwards from today, including today) in which the stock price is less than or equal to today’s price.

For example, if the stock price for the next seven days is [100, 80, 60, 70, 60, 75, 85], then the stock span will be [1, 1, 1, 2, 1, 4, 6].

Example:

Input:"StockSpanner"."next"."next"."next"."next"."next"."next"."next"], [[], [100], [80], [60], [70], [60], [75], [85] output: [null.1.1.1.2.1.4.6First, initialize S = StockSpanner(), then: s.next ()100) is called and returns1, S.n ext (80) is called and returns1, S.n ext (60) is called and returns1, S.n ext (70) is called and returns2, S.n ext (60) is called and returns1, S.n ext (75) is called and returns4, S.n ext (85) is called and returns6.Copy the code

Note (for example) that s.ext (75) returns4Because at the end of the day4Price (including today's price75) less than or equal to today's price.Copy the code

Tip:

When stockSpanner.next (int price) is called, there will be1 <= price <= 10^5. Each test case can be invoked at most10000Time StockSpanner. Next. Of all test cases, most calls150000Time StockSpanner. Next. The total time limit for this problem has been reduced50%.Copy the code

Their thinking

As the problem implies, if we want the number of elements that are smaller (or equal) than the current element, and the number of elements includes itself, then we should add one more to our final result.

For example, for example 6,1,2,3,4,9, we work backwards. When we insert 9, if we find that the previous 4 is less than 9, does that mean that the number less than 9 is equal to the number less than 4 plus 1? This is wrong, however, because the 6 in the first place is smaller than 9 but larger than 4, so by the end of the number 4, there is no comparison between 6 and 9 in the number less than 4.

So, we’re going to jump to 6 and figure out what’s less than or equal to ourselves.

var StockSpanner = function() {
    // Store stock span
    this.spanner = []
    // Store stock prices
    this.stockPrice = []
};

/ * * *@param {number} price
 * @return {number}* /
StockSpanner.prototype.next = function(price) {
    // Make a special judgment on the first day
    if(!this.spanner.length){
        this.spanner.push(1)
        this.stockPrice.push(price)
        // Return 1 directly
        return 1
    }
    let cnt = 0
    let idx = this.stockPrice.length-1
    while(price >= this.stockPrice[idx] && idx>=0){
        cnt += this.spanner[idx]
        idx -= this.spanner[idx]
    }
    // Plus itself
    cnt++
    // Perform an update operation to push the current stock price and span to the stack
    this.spanner.push(cnt)
    this.stockPrice.push(price)
    return cnt
};

/** * Your StockSpanner object will be instantiated and called as such: * var obj = new StockSpanner() * var param_1 = obj.next(price) */
Copy the code

739. Daily temperature

739. Daily temperature problem portal

Topic describes

Generate a new list based on the daily temperature list. The output of the corresponding position is: the minimum number of days to wait for higher temperatures to be observed. If the temperature does not rise after that point, substitute 0 at that point.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output would be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.

Their thinking

In this case, we use the monotone stack idea, reducing the time complexity from O(n^2) to O(n).

All we need to do is maintain a new stack, and we’re going to iterate through the array, and as long as the stack is not empty, if the current number is greater than the top element, it’s going to be the first element that’s greater than it, and we’re just going to figure out the difference, and then we’re going to store the result.

The new stack is maintained to store our element subscripts, so that we can easily find the distance, in this case, I think it can be said to be a template problem of monotonous stack. There will be other topics on monotone stack later in the column, you can refer to ha.

/ * * *@param {number[]} T
 * @return {number[]}* /
var dailyTemperatures = function(T) {
    let stack = []
    // Initializes the temperature list, default is 0
    let res = new Array(T.length).fill(0)
    for(let i=0; i<T.length; i++){// Compare the value of the subscript of the top element to the current element
        while(T[i] > T[stack[stack.length-1]] && stack.length){
            let idx = stack.pop()
            res[idx] = i-idx
        }
        stack.push(i)
    }
    return res
};
Copy the code

907. Sum of minimum values of subarrays

907. Sum of minimum values of subarrays to original problem portal

Topic describes

Given an integer array A, find the sum of min(B), where the range of B is each (consecutive) subarray of A.

Since the answer may be large, return the answer module 10^9 + 7.

Example:

Input:3.1.2.4] output:17The subarray is [3], [1], [2], [4], [3.1], [1.2], [2.4], [3.1.2], [1.2.4], [3.1.2.4]. The minimum value for3.1.2.4.1.1.2.1.1.1, and for17.Copy the code

Tip:

1 <= A <= 30000
1 <= A[i] <= 30000
Copy the code

Their thinking

Carrying Jack-108

The sum of the smallest subarrays is the number of arrays that can be formed with A[I] as the smallest.

For example, [2,4,1,2], with 1 as the smallest number. The number of arrays that can be formed is (2+1)*(1+1), where 2 means 1 has two larger numbers to its left and 1 means 1 has one larger number to its right.

The monotone stack is used to find the number corresponding to A[I] that is nearest to smaller than A[I]. The index is prev,next, and A[I] is the array that the smallest number can form

(i-prev[i])*(next[i]-i)
Copy the code

I’m not adding 1 here, because prev[I] is already smaller than A[I], and any number that can form an array with A[I] is larger than A[I].

The way I did it:

The comment is detailed enough, but I refer to the problem of the big guy’s code, but I directly calculate the number of subarrays with the current A[I] as the minimum value is greater than or equal to the current value. So you can just multiply the sum. (If the value is greater than or equal to on the left, the value must be greater than or equal to on the right.)

I don’t understand why the big guy initializes -1 on the left and a.Length on the right. If we have A situation where the left side is larger than the current A[I], then we maintain A monotonically decreasing stack that keeps going up and down until the stack is empty, at which point the left side should be I +1. Personally, I feel that it is easier to understand what I wrote, otherwise I will directly make a -1, the first time I use monotonous stack, or I am not familiar with it.

When the right-hand side is larger than the current A[I], the monotonically decrement stack we maintain will continue to exit and exit until the stack is empty, in which case the right-hand side should be a. length-i (the reason for not +1 is to count from 0). So this part of the big head set as A. Length is very clever, still clear.

/ * * *@param {number[]} A
 * @return {number}* /
var sumSubarrayMins = function(A) {
  let mod = 1e9+7
  // Maintain a stack
  let stack = []
  // Find the number of subarrays where A[I] is greater than or equal to itself
  let prev = []
  for(let i=0; i<A.length; i++){while(stack.length && A[stack[stack.length-1]] >= A[i]) stack.pop()
    // Return I +1 if the stack is empty, i.e., the left side is larger than itself, otherwise return I - the top element of the stack (i.e., the saved subscript value)
    prev[i] = stack.length ? i - stack[stack.length-1] : i+1
    stack.push(i)
  }
  stack = []
  // Find the number of subarrays whose minimum value is A[I] greater than itself (no equal sign because equal values are not double-counted)
  let nextv = []
  for(let i=A.length-1; i>=0; i--){while(stack.length && A[stack[stack.length-1]] > A[i]) stack.pop()
    // return a.length -i if the stack is empty, that is, the right-hand side is larger than itself, otherwise return the top element of the stack (that is, the saved subscript value) -i
    nextv[i] = stack.length? stack[stack.length-1] - i : A.length-i
    stack.push(i)
  }
  let sum = 0
  for(let i=0; i<A.length; i++){Prev [I]* nexTV [I] = prev[I]* nexTV [I
    sum += (prev[i]*nextv[i]*A[i])
    // Do the modulo operation
    sum %= mod
  }
  return sum
};
Copy the code

Reverse the substring between each pair of parentheses

Reverse the substring source portal between each pair of parentheses

Topic describes

Give a string s (lowercase letters and parentheses only).

Invert each pair of matching strings layer by layer in the order from inside the brackets to outside, and return the final result.

Note that your results should not contain any parentheses.

Example 1:

Enter: s ="(abcd)"Output:"dcba"
Copy the code

Example 2:

Enter: s ="(u(love)i)"Output:"iloveu"
Copy the code

Example 3:

Enter: s ="(ed(et(oc))el)"Output:"leetcode"
Copy the code

Example 4:

Enter: s ="a(bcdefghijkl(mno)p)q"Output:"apmnolkjihgfedcbq"
Copy the code

Tip:

0 <= s.length <= 2000There's only lowercase and parentheses in the s and we're going to make sure that all parentheses come in pairsCopy the code

Their thinking

Initialize the stack, top element is “” encounter ‘(‘: push an empty string to the top of the stack encounter ‘)’: flip the last element at the top of the stack + the penultimate element at the top of the stack encounter character: directly spell the last element at the top of the stack with it

See Tuotuoli

Example stack array operation diagram:

Example: a(bcdefghijkl(mno)p)q ['a'] (['a'.' ']
b ['a'.'b']
c ['a'.'bc']
d ['a'.'bcd']
e ['a'.'bcde']
f ['a'.'bcdef']
g ['a'.'bcdefg']
h ['a'.'bcdefgh']
i ['a'.'bcdefghi']
j ['a'.'bcdefghij']
k ['a'.'bcdefghijk']
l ['a'.'bcdefghijkl'] (['a'.'bcdefghijkl'.' ']
m ['a'.'bcdefghijkl'.'m']
n ['a'.'bcdefghijkl'.'mn']
o ['a'.'bcdefghijkl'.'mno'[])'a'.'bcdefghijklonm']
p ['a'.'bcdefghijklonmp'[])'apmnolkjihgfedcb']
q ['apmnolkjihgfedcbq']
Copy the code

/ * * *@param {string} s
 * @return {string}* /
var reverseParentheses = function(s) {
  let stack = [' ']
  for(let i=0; i<s.length; i++){let ch = s[i]
    if(ch === '('){
      stack.push(' ')}else if(ch === ') ') {let str = stack.pop()
      let tmp = str.split(' ').reverse().join(' ')
      stack[stack.length-1] += tmp
    }else{
      stack[stack.length-1] += ch
    }
  }
  return stack.pop()
};
Copy the code

1249. Remove invalid parentheses

1249. Removed invalid parenthesis portal

Topic describes

You are given a string s composed of ‘(‘, ‘)’ and lowercase letters.

You need to remove the minimum number of ‘(‘ or ‘)’ (you can remove parentheses anywhere) from the string to make the rest of the ‘parenthesis string’ valid.

Please return any valid string.

A valid “parenthesis string” should meet any of the following requirements:

Empty strings or strings containing only lowercase letters can be written as strings AB (A concatenates B), where both A and B are valid “parenthesis strings” can be written as strings (A), where A is A valid “parenthesis string”

Example 1:

Enter: s ="lee(t(c)o)de)"Output:"lee(t(c)o)de"Explanation:"lee(t(co)de)" , "lee(t(c)ode)"It's also a possible answer.Copy the code

Example 2:

Enter: s ="a)b(c)d"Output:"ab(c)d"
Copy the code

Example 3:

Enter: s =")) (("Output:""Explanation: Empty strings are also validCopy the code

Example 4:

Enter: s ="(a(b(c)d)"Output:"a(b(c)d)"
Copy the code

Tip:

1 <= s.length <= 10^5S [I] is likely to be'(',') 'Or English lowercase lettersCopy the code

Their thinking

At first I thought I would just get rid of the extra close parentheses if the corresponding parentheses matched, but in this example I can’t pass because the open parentheses don’t match. So I want to save the string index corresponding to the parentheses. At first, we can delete the mismatched close parentheses as the original method, and delete the index corresponding to the open parentheses. Finally, we can delete all the extra index values, so that there will not be any left open parentheses.

Do not use splice to delete elements with specified subscripts. Splice will change the length of the array that you are storing subscripts based on. Arr =arr.filter(item=>item)

Finally, the res.join(“) method converts the array to the desired string.

var minRemoveToMakeValid = function(s) {
    let res = [...s]
    let stack = []
    for(let i=-0; i<s.length; i++){let ch = s[i]
        if(ch === '('){
            stack.push(i)
        }else if(ch === ') ') {if(stack.length) stack.pop()
            else delete(res[i])
        }
    }
    while(stack.length){
        let idx = stack.pop()
        delete(res[idx])
    }
    res = res.filter(item= >item)
    return res.join(' ')};Copy the code

The queue

933. Number of recent requests

933. Last number of requests original problem portal

Topic describes

Write a RecentCounter class to count the most recent request.

It has only one method: ping(int t), where t stands for some time in milliseconds.

Returns the number of pings from 3000 ms ago to the present.

Any pings within the [T-3000, t] time range will be counted, including current pings.

Make sure that each call to ping uses a larger t value than before.

Example:

Inputs: Inputs = ["RecentCounter"."ping"."ping"."ping"."ping"], inputs = [[],[1], [100], [3001], [3002] output: [null.1.2.3.3]
Copy the code

Tip:

Ping can be invoked a maximum of 10000 times per test case. Each test case calls ping with a strictly increasing t value. Each call to ping has 1 <= t <= 10^9.

Answer key

According to the sample, it is found that the earlier the request is sent, the earlier the request is not included in the 3000ms request

For fifO, consider using queues

New requests are enqueued, and requests made before 3000ms are enqueued

The length of the queue is the number of recent requests.

var RecentCounter = function() {
    this.queue = []
};

/ * * *@param {number} t
 * @return {number}* /
RecentCounter.prototype.ping = function(t) {
  // Queue the new request
  this.queue.push(t)
  // the request sent before 3000ms is queued
  while(this.queue[0] < t-3000) {this.queue.shift()
  }
  return this.queue.length
};

/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
Copy the code

The list

2. Add two numbers

2. Add two numbers to the original problem portal

Topic describes

Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit.

If we add these two numbers together, a new linked list is returned to represent their sum.

You can assume that neither of these numbers will start with 0, except for the number 0.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) output:7 -> 0 -> 8The reason:342 + 465 = 807
Copy the code

Their thinking

Create a new linked list, pay attention to the carry, because in this case according to the reverse order to output, directly start traversal from the beginning node, one of the two linked list is empty node, directly set to 0.

And also, notice that the last carry is something to judge.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function (l1, l2) {
    let sum = 0;
    let head = new ListNode('head'); / / head node
    let p = head;
    let cnt = 0; / / carry
    while (l1 || l2) {
        let ans = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + cnt;
        cnt = ans >= 10 ? 1 : 0;
        p.next = new ListNode(ans % 10);
        p = p.next;
        l1 && (l1 = l1.next);
        l2 && (l2 = l2.next);
    }
    cnt && (p.next = new ListNode(cnt));
    return head.next;
};
Copy the code

206. Reverse linked lists

206. Reverse the linked list portal

Topic describes

Reverse a single linked list.

Example:

Input:1->2->3->4->5- > NULL output:5->4->3->2->1->NULL
Copy the code

Advancements: You can iterate or recursively reverse linked lists. Can you solve the problem in two ways?

Their thinking

Non-recursive solution

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur){
        let tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
};
Copy the code

The recursive method

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function (head) {
    let reverse = (pre, cur) = > {
        if(! cur)return pre;
        let tmp = cur.next;
        cur.next = pre;
        return reverse(cur, tmp);
    }
    return reverse(null, head);
};
Copy the code

92. Reverse linked list II

Reverse the linked list II portal

Topic describes

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 = 4Output:1->4->3->2->5->NULL
Copy the code

Their thinking

With the aid of recursion

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}* /
var reverseBetween = function (head, m, n) {
    let reverse = (pre, cur) = > {
        if(! cur)return pre;
        let tmp = cur.next;
        cur.next = pre;
        return reverse(cur, tmp);
    }
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let p = dummyHead;
    let k = m - 1;
    // Find the precursor node that needs to be reversed
    while (k--) {
        p = p.next;
    }
    // Save the precursor node
    let front = p;
    // Find the head node that needs to be reversed
    let frontNode = front.next;
    k = n - m + 1;
    // Find the last node that needs to be reversed
    while (k--) {
        p = p.next;
    }
    // Find the last node that needs to be reversed
    let endNode = p;
    // Save the successor node
    let end = endNode.next;
    // Start reversing the list by setting the subsequent value to empty
    endNode.next = null;
    front.next = reverse(null, frontNode);
    // The original head node of the reversed list section is now the tail node, pointing to the original successor node
    frontNode.next = end;
    return dummyHead.next;
};
Copy the code

Iterative method

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}* /
var reverseBetween = function(head, m, n) {
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let p = dummyHead;
    let k = m-1;
    // Find the precursor node that needs to be reversed
    while (k--) {
        p = p.next;
    }
    // Save the precursor node
    let front = p;
    let pre = frontNode = front.next;
    let cur = pre.next;
    k = n-m;
    // A list of length 3 needs to be reversed 2 times, so a list of length n needs to be reversed n-1 times
    while(k--){
        let tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    // Point the next of the original precursor node to the current reversed list
    front.next = pre;
    // The head node of the reversed list is now the tail node pointing to the next node
    frontNode.next = cur;
    return dummyHead.next;
};
Copy the code

203. Remove linked list elements

203. Remove the linked list element portal

Topic describes

Deletes all nodes in the linked list that are equal to the given value val.

Example:

Input:1->2->6->3->4->5->6, val = 6Output:1->2->3->4->5
Copy the code

Their thinking

Create a new list and, in case of the same value, point next of the current node to next of the next node, otherwise continue traversing.

var removeElements = function(head, val) {
    let dummyHead = new ListNode(); / / dumb nodes
    dummyHead.next = head;
    let p = dummyHead;
    while(p.next){
        if(p.next.val === val){
            p.next = p.next.next;
        }else{ p = p.next; }}return dummyHead.next;
};
Copy the code

Swap nodes in a linked list in pairs

24. Switch switches in pairs between nodes in the linked list

Topic describes

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.

Example:

For a given1->2->3->4, you should return2->1->4->3.
Copy the code

Their thinking

Non-recursive solution

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    if(head == null || head.next == null) return head;
    let hummyHead = new ListNode(); // Virtual node
    hummyHead.next = head;
    let p = hummyHead;
    let node1,node2; // The current two nodes to swap
    while((node1 = p.next) && (node2 = p.next.next)){
        // Perform the switch operation
        node1.next = node2.next;
        node2.next = node1;
        // string the list together
        p.next = node2;
        p = node1;
    }
    return hummyHead.next;
};
Copy the code

The recursive method

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function (head) {
    if(! head || ! head.next)return head;
    let node1 = head, node2 = head.next;
    node1.next = swapPairs(node2.next);
    node2.next = node1;
    return node2;
};
Copy the code

18. Remove nodes from the list

18. Remove the linked list node from the original topic portal

Topic describes

Given a head pointer to a one-way linked list and the value of a node to delete, define a function to delete that node.

Returns the head node of the deleted list.

Note: this question has been changed from the original question

Example 1:

Enter: head = [4.5.1.9], val = 5Output:4.1.9Given that the value in your linked list is5After calling your function, the strain of the list is4 -> 1 -> 9.
Copy the code

Example 2:

Enter: head = [4.5.1.9], val = 1Output:4.5.9Given that the value in your linked list is1After calling your function, the strain of the list is4 -> 5 -> 9.
 
Copy the code

Description:

If you use C or C++, you don’t need to free or delete the deleted node

Their thinking

Create a new list and, in case of the same value, point next of the current node to next of the next node, otherwise continue traversing.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var deleteNode = function(head, val) {
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let p = dummyHead;
    while(p.next){
        if(p.next.val === val){
            p.next = p.next.next;
        }else{ p = p.next; }}return dummyHead.next;
};
Copy the code

Delete the penultimate node of the linked list

19. Delete the NTH node from the list

Topic describes

Given a linked list, delete the NTH last node of the list and return the first node of the list.

Example:

Given a linked list:1->2->3->4->5, and n =2.When the penultimate node is deleted, the linked list becomes1->2->3->5.
Copy the code

Description:

A given n is guaranteed to be valid.

Advanced:

Can you try using a scan implementation?

Their thinking

Double pointer, first let a pointer Q take n steps, then the other pointer P together, when the first pointer Q comes to the end, then p pointer points to the node we want to delete, delete it.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
    let dummyHead = new ListNode();
    dummyHead.next = head;
    let p = dummyHead;
    let q = dummyHead;
    let k = n;
    while(k--) q = q.next; // let a pointer take n steps first
    while(q.next){ / / go together
        q = q.next;
        p = p.next;
    }
    p.next = p.next.next; // Find the deleted node and delete it
    return dummyHead.next;
};
Copy the code

142. Circular linked List II

142. Circular linked list II original problem portal

Topic describes

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.

Advanced:

Can you solve this problem without extra space?

Example 1:

Enter: head = [3.2.0, -4], pos = 1Output: Returns the index as1A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0Output: Returns the index as0A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = -1Output: returnnullExplanation: There are no rings in the linked list.Copy the code

Tip:

• The number of nodes in a linked list ranges from[0, 104] 内
• -10^5 <= Node.val <= 10^5
• The value of pos is -1 or a valid index in the linked list

Their thinking

Two fast and slow Pointers, starting from the beginning node, if the list has a ring, the fast pointer can certainly meet the slow pointer in the ring. Without the ring, it is impossible to meet again. The encounter must be within the ring.

When meeting, the slow pointer goes:D+S1D+S1

Assuming that the fast pointer has gone around the ring n times when it meets, the distance it travels is: D+n(S1+S2)+S1D+n(S1+S2)+S1

Since the fast pointer is twice as fast, the distance traveled in the same time is also twice:

D+n(S1+S2)+S1 = 2(D+S1)

We get :(n-1)S1+ nS2=D

We don’t care how many times the fast Pointers have gone around by the time they meet, we take n = 1 and cancel S1:

D=S2

Then, when the fast and slow Pointers meet for the first time, put the fast Pointers back to the head node. Since D=s2, we move the fast and slow Pointers together, each taking one step, and they will inevitably reach the entry point of the ring and then meet. At this point, the corresponding pointer subindex can be returned.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    let fast = head, low = head; // First, all the head nodes appear
    while(fast){ // Make sure loops exist
        if(fast.next == null)  return null; // fast.next null indicates no loop
        low = low.next; // Slow the pointer one step
        fast = fast.next.next; // Fast pointer takes two steps
        if(low == fast){ // For the first time
            fast = head; // Fast pointer returns to the head node
            while(true) {if(fast == low){
                    return low;
                }
                fast = fast.next; // The fast and slow Pointers go togetherlow = low.next; }}}return null;
};
Copy the code

Refer to the illustration of the Stupid Pig blast group

In this paper, the reference

• How does the front end prepare data structures and algorithms?
• Write front-end algorithm advanced guide, I am how two months zero basis brush 200 questions
• (1.8W word) How do front-end engineers systematically practice data structures and algorithms? 【 the 】

conclusion

❤️ follow + like + favorites + comments + forward ❤️, original is not easy, your support will be my biggest motivation ~

Visit the oratory blog for convenient reading and playing

Finally, wish you a happy New Year, the Year of the Ox and good luck. You can finish the spring recruitment as soon as possible and get the offer soft. I hope my article can help you

If this article is not authorized by the author, it is forbidden to reprint, if found the same, will be held responsible!

【 Author: Chocolate】juejin.cn/user/298153…