写给零基础的前端算法入门指南，acmer带女友刷80+【栈与队列与链表篇】
共 8834字，需浏览 18分钟
·
2021-02-11 09:56
前言
之前的文章大部分都是写给女友系列，但有一段时间没有进行更新了，一方面春招要准备开始了，另一方面女友还在准备年前面试，面试之后的复盘总结是挺重要的。
访问 HearLing的个人主页 会持续分享前端知识体系。
好像越要到过年了，一些写作时间还多了起来，现在和大家分享一下我们是如何准备算法这一块的，正好春招即将开启，年前还能最后准备一下，希望对大家有所帮助。
本文若未经作者授权，禁止转载，如若发现雷同，必将追究责任到底！
原本打算通过一篇文章介绍一下，推荐一下自己的刷题方式和刷题路线，得到一些伙伴的反馈：最好还是更加详细，面向零基础，小白这些，还有github访问速度也是一方面问题，可能图片都加载不出来。
因此，我打算分模块出几期文章，这样你只用通过首发在掘金的文章即可了解 Chocolate 同学整体刷题汇总啦。马上就要过年了，希望能够帮助你的春招。打算出的内容计划安排如下：
🐮写给零基础的前端算法入门指南，acmer带女友刷80+【栈与队列与链表篇】（本期已完成🎉） 🐮写给零基础的前端算法入门指南，acmer带女友刷80+【递归与回溯篇】 🐮写给零基础的前端算法入门指南，acmer带女友刷80+【双指针与字符串篇】 🐮写给零基础的前端算法入门指南，acmer带女友刷80+【二叉树篇】 🐮写给零基础的前端算法入门指南，acmer带女友刷80+【动态规划DP篇】 🐮写给零基础的前端算法入门指南，acmer带女友刷80+【总结篇】
算法这一块到底如何准备
首先，我来简单介绍一下自己，在校打过ACM（如果没听过，当我没说，因为没有很大价值的牌牌，铁牌，参赛证以及证书倒是一堆）
如果你知道acm，并且参与过，对于国内前端（注意是说前端）面试的话，应该不需要花费很长的刷题时间，如果大家有想法了解我的acm经历的话，这个后续我会考虑在 B站发布一期视频。
那么对于零基础的小白来说，可能需要花10-20天左右时间来准备算法，而对于非科班来说这个周期可能会更长一点。那么，现在我准备来分享我是如何带着女友零基础刷题的。
第一点，明确算法它不是很难的东西，理解了其实就那会事，或许你还会喜欢上做题，当然，对于acm大佬做的题就另当别论了，这篇文章主体与面试水平为准 第二点，前端对于算法这一块的考察相对来说会偏简单一点，我在春秋招过程中遇到的笔试题都是一些常见的题目，比如搜索，贪心，简单动态规划，经典排序算法，都是以 leetcode一些简单以及中等难度的居多，而这些算法对于科班来说的话，应该在学校都学习过，比如算法分析与设计，数据结构与算法这一类课程，那么有这个基础，你的刷题时间又可以进行缩短了第三点，既然说到要刷题，该如何刷，我在掘金参考了几个大佬（文末有参考处），大家都会推荐分专题来刷，在这里，我也是非常推荐的，在这里，我希望的是将刷算法题的数量再减少一点，带你入门，当你刷完这些专题之后，你就有相关思维能力主动去刷题了，而不是很被动的去刷，这样也很方便自己总结归纳~ 其它，可以参考大佬的文章，这里不再赘述...
一份思维导图，让你的刷题路线更简单
开门见山地说，首先提供一份思维导图，让知识由繁到简。
获取高清PDF，请在微信公众号【小狮子前端】回复【LeetCode】，一起刷题或者交流学习可以加企鹅群【666151691】
本仓库刷题路线参考 ssh （给大佬点赞） 仓库地址：https://github.com/sl1673495/leetcode-javascript
感谢大佬的归纳总结，原本打算在大佬那里打卡学习，后面考虑不太友好，还是自己新建了一个仓库打卡学习。
其次，本仓库解题代码大部分是自己的代码风格，题量也进行了拓展，将会持续更新下去，何不star收藏一下？
仓库介绍
仓库地址：https://github.com/Chocolate1999/leetcode-javascript
本仓库将全程使用的语言是 JavaScript，是一个纯前端刷题路线，对于前端刷题没有方向的小伙伴简直是福音。解题代码会记录在本仓库的 Issues 中，会按照 label进行分类。比如想查看 「递归与回溯」 分类下的问题，那么选择标签进行筛选即可。
同时，小伙伴们可以在 Issues 中提交自己的解题代码，🤝 欢迎 Contributing ，可打卡刷题，坚持下来的人最酷！Give a ⭐️ if this project helped you !
刷题路线
下面正式开始我们的刷题之路，给本篇文章点个赞，拿出自己心仪的键盘，开始！
以下专题顺序仅个人以及面试高频点来总结的刷题方式，大家可以根据自己的想法来组合。更多题集请参考本仓库哈~
栈
20. 有效的括号
20. 有效的括号原题传送门
「题解」
发现越靠后的左括号，最先匹配，也就是后进先出的思想，于是考虑使用栈这个数据结构。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
// 如果是奇数，不可能匹配成功，直接返回false
if(s.length & 1) return false
let stack = []
for(let i=0;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
};
946. 验证栈序列
946. 验证栈序列原题传送门
「题目描述」
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
「解题思路」
借助一个新栈来存放入栈的元素，然后每次和出栈的元素进行比对，如果匹配成功，双方进行出栈操作，最后，如果这个新栈为空，那么代表这个栈入栈和出栈序列是合理的，返回 true，否则返回false
/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
// 借助一个新的栈
let stack = []
for(let cur of pushed){
// 存放入栈的元素
stack.push(cur)
// 和出栈元素进行比对，如果匹配都弹出栈
while(stack[stack.length-1] === popped[0] && stack.length){
stack.pop()
popped.shift()
}
}
return !stack.length
};
921. 使括号有效的最少添加
921. 使括号有效的最少添加原题传送门
「题目描述」
给定一个由'(' 和')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())"
输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()"
输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。
「解题思路」
借助一个新栈，然后遍历当前字符串，如果当前栈顶元素和目前字符括号匹配，则弹出栈顶元素，否则进行入栈操作，最后需要的括号数即为栈剩余的元素个数
/**
* @param {string} S
* @return {number}
*/
var minAddToMakeValid = function(S) {
// 长度为0，无须添加
if(!S.length) return 0
let stack = []
for(let i=0;i let ch = S[i]
// 如果当前栈顶元素和目前字符括号匹配，则弹出栈顶元素
if(ch === ')' && stack[stack.length-1] === '(') stack.pop()
else stack.push(ch)
}
// 栈的剩余元素个数，即需要的括号数
return stack.length
};
901. 股票价格跨度
901. 股票价格跨度原题传送门
「题目描述」
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是[100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是[1, 1, 1, 2, 1, 4, 6]。
示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
提示：
调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。
「解题思路」
正如题意，我们要求当前元素之前，比自己小（可以相等）的元素个数，并且元素个数包括本身，那么我们最后的结果应该还要加1.
于是按题意，我们采用跨度法，举个例子，对于例子6，1，2，3，4，9，从后往前逆推一下，当我们新插入9的时候，如果发现前一位的4比9小，那么是否说明比9小的数量就等于比4小的数量加1？然而这是错的，因为首位的6比9小，却比4大，因此截止数字的4时候，比4小的数量中并不包含6与9的对比。
因此，我们还要跳到 6 的位置再去计算小于等于自己的元素。
var StockSpanner = function() {
// 存储股票跨度
this.spanner = []
// 存储股票价格
this.stockPrice = []
};
/**
* @param {number} price
* @return {number}
*/
StockSpanner.prototype.next = function(price) {
// 对于第一天进行特殊判断
if(!this.spanner.length){
this.spanner.push(1)
this.stockPrice.push(price)
// 直接返回1
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]
}
// 加上本身
cnt++
// 进行更新操作，将当前股票价格和跨度入栈
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)
*/
739. 每日温度
739. 每日温度原题传送门
「题目描述」
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
「解题思路」
本题用到了单调栈的思路，将原本需要 O(n^2) 的时间复杂度降低到了 O(n)。
我们只需要维护一个新栈，首先遍历整个数组，只要栈不为空，如果当前的数字大于栈顶元素，则必定是第一个大于它的元素，我们只需要求出相差距离，然后存入结果就好了。
维护的新栈存放的是我们的元素下标，这样我们求距离时就很方便了，本题我觉得可以说是单调栈的一个模板题。专栏后续会有单调栈其它题目，可以查阅哈。
/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function(T) {
let stack = []
// 初始化气温列表，默认值为0
let res = new Array(T.length).fill(0)
for(let i=0;i //将栈顶元素下标对应的值和当前元素进行比较
while(T[i] > T[stack[stack.length-1]] && stack.length){
let idx = stack.pop()
res[idx] = i-idx
}
stack.push(i)
}
return res
};
907. 子数组的最小值之和
907. 子数组的最小值之和原题传送门
「题目描述」
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
示例：
输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000
「解题思路」
搬运 jack-108大佬的题解：
既然是求子数组中最小值的和，就是求 以 A[i] 作为最小数能构成的数组有多少个。
比如 [2,4,1,2] ,以1 为最小数。能构成的数组数为 (2+1)*(1+1) ，2 表示 1左面有两个比它大的数，1 表示 1 右面有一个比它大的数。
用单调栈求出 A[i] 对应的左右最近比 A[i] 小的数，记索引为 prev,next，A[i]为最小数能形成的数组为
(i-prev[i])*(next[i]-i)
这里为什么没有加 1 了呢，因为 prev[i]已经是比 A[i] 小的数了，能和 A[i] 形成数组的都是比 A[i] 大的数。
「我的解题方式：」
注释已经足够详细，还是补充一下，我参考了大佬的解题代码，只不过我是直接求出来了以当前 A[i] 为最小值的子数组左右两边 大于或等于当前值的个数。这样后续求和直接相乘即可。（不过这里要「强调一下」，如果左边设置大于等于了，右边就只能是大于了，不然会重复计算相等的值）
开始有点看不懂大佬为啥左边初始化为 -1，右边初始化为 A.length 。假如我们遇到了这种情况，左边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时左边个数应该为 i+1（从 0 开始计数嘛），那么这部分大佬设为 -1 就很巧妙了，问题也就自然明白啦，个人感觉自己写的还是比较好理解一点，不然直接弄一个 -1 ，第一次用单调栈，还是不太熟...
那么对于右边初始化为 A.length ，也是同理啦，当右边都比当前 A[i] 要大，那我们维护的单调递减栈就会不断出栈，不断出栈，直到栈为空为止，此时右边个数应该为 A.length-i（不用+1的原因是从0计数），那么这部分大佬设为 A.length 就很巧妙了，依旧清晰明了。
/**
* @param {number[]} A
* @return {number}
*/
var sumSubarrayMins = function(A) {
let mod = 1e9+7
// 维护一个栈
let stack = []
// 求以A[i]为最小值的子数组左边大于或等于自己的个数
let prev = []
for(let i=0;i while(stack.length && A[stack[stack.length-1]] >= A[i]) stack.pop()
// 如果栈为空，即左边都比自己大，则返回i+1，否则返回i-栈顶元素（即保存的下标值）
prev[i] = stack.length ? i - stack[stack.length-1] : i+1
stack.push(i)
}
stack = []
// 求以A[i]为最小值的子数组右边大于自己的个数（没有等号是因为不会重复计算相等的值）
let nextv = []
for(let i=A.length-1;i>=0;i--){
while(stack.length && A[stack[stack.length-1]] > A[i]) stack.pop()
// 如果栈为空，即右边都比自己大，则返回A.length-i，否则返回栈顶元素（即保存的下标值）-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[i] 为最小值的子数组的组合共有prev[i]*nextv[i]种情况，那么和的话乘以A[i]累加即可
sum += (prev[i]*nextv[i]*A[i])
// 按题意，进行取模运算
sum %= mod
}
return sum
};
1190. 反转每对括号间的子串
1190. 反转每对括号间的子串原题传送门
「题目描述」
给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例 1：
输入：s = "(abcd)"
输出："dcba"
示例 2：
输入：s = "(u(love)i)"
输出："iloveu"
示例 3：
输入：s = "(ed(et(oc))el)"
输出："leetcode"
示例 4：
输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"
提示：
0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
「解题思路」
初始化栈，栈顶元素为 " "
遇到'(': 向栈顶压入空字符串
遇到')': 把栈顶的最后一个元素翻转 + 栈顶倒数第二个元素
遇到 字符: 直接将栈顶最后一个元素与它拼上
参考 tuotuoli 大佬解题思路
样例栈数组操作示意：
样例：a(bcdefghijkl(mno)p)q
a ['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']
/**
* @param {string} s
* @return {string}
*/
var reverseParentheses = function(s) {
let stack = ['']
for(let i=0;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()
};
1249. 移除无效的括号
1249. 移除无效的括号原题传送门
「题目描述」
给你一个由'('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')'（可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
示例 1：
输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：
输入：s = "a)b(c)d"
输出："ab(c)d"
示例 3：
输入：s = "))(("
输出：""
解释：空字符串也是有效的
示例 4：
输入：s = "(a(b(c)d)"
输出："a(b(c)d)"
提示：
1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母
「解题思路」
一开始我是想着只要对应括号匹配就好了，将多余的右括号删掉，但是这个样例 ))(( 不可能过的，因为左括号也可以不匹配呀。于是我想着将括号对应字符串索引存起来，起初我们可以将不匹配的右括号还是按原来方法删掉就好了，匹配一个就删掉一个对应左括号的索引值，最后多出来的索引值全删掉就好了，这样就不会出现左括号还余留的情况。
这里提示一下：不要用 splice去删除指定下标的元素，splice会改变原数组长度，而你原本存的下标是基于原数组的。delete方法不会改变数组长度，但删除的那个位置会变成'undefined'，所以我们用fliter方法过滤一遍出有效值 arr=arr.filter(item=>item)
最后通过 res.join('') 方法，将数组转换成我们最后要的字符串即可。
var minRemoveToMakeValid = function(s) {
let res = [...s]
let stack = []
for(let i=-0;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('')
};
队列
933. 最近的请求次数
933. 最近的请求次数原题传送门
「题目描述」
写一个RecentCounter 类来计算最近的请求。
它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。
返回从 3000毫秒前到现在的 ping 数。
任何处于[t - 3000, t]时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。
保证每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出：[null,1,2,3,3]
提示：
每个测试用例最多调用10000次 ping。每个测试用例会使用严格递增的 t值来调用 ping。每次调用 ping 都有1 <= t <= 10^9。
「题解」
根据样例，发现越早发出的请求越早不在 3000ms 内的请求里
满足「先进先出」，考虑用队列
那么就将新请求加入队列，3000ms前发出的请求就出队列
队列的长度即为最近请求次数。
var RecentCounter = function() {
this.queue = []
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function(t) {
// 将新请求加入队列
this.queue.push(t)
// 3000ms 前发出的请求就出队列
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)
*/
链表
2. 两数相加
2. 两数相加原题传送门
「题目描述」
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 「逆序」 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
「解题思路」
模拟相加，创建一个新的链表，注意一下进位，由于本题按照逆序来输出的，直接从头结点开始遍历就好了，两个链表其中一个为空节点，直接置为0即可。
同时，要注意，最后一个进位的情况，要进行判断一下。
/**
* 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'); // 头结点
let p = head;
let cnt = 0; // 进位
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;
};
206. 反转链表
206. 反转链表原题传送门
「题目描述」
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
「解题思路」
「非递归解法」
/**
* 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;
};
「递归解法」
/**
* 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);
};
92. 反转链表 II
92. 反转链表 II原题传送门
「题目描述」
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
「解题思路」
「借助递归」
/**
* 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;
// 先找到需要反转链表部分的前驱节点
while (k--) {
p = p.next;
}
// 保存前驱节点
let front = p;
// 找到需要反转链表部分的头节点
let frontNode = front.next;
k = n - m + 1;
// 再找到需要反转链表部分的尾节点
while (k--) {
p = p.next;
}
// 找到需要反转链表部分的尾节点
let endNode = p;
// 保存后继节点
let end = endNode.next;
// 将后继值为空，开始反转链表
endNode.next = null;
front.next = reverse(null, frontNode);
// 原本的反转链表部分的头节点现在变成了尾节点，指向原本的后继节点
frontNode.next = end;
return dummyHead.next;
};
「迭代解法」
/**
* 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;
// 先找到需要反转链表部分的前驱节点
while (k--) {
p = p.next;
}
// 保存前驱节点
let front = p;
let pre = frontNode = front.next;
let cur = pre.next;
k = n-m;
// 长度为3的链表需要反转2次，那么长度为n的链表需要反转n-1次
while(k--){
let tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
// 将原本前驱节点的next指向当前反转后的链表
front.next = pre;
// 原本反转链表的头节点现在变成了尾结点，指向后继节点
frontNode.next = cur;
return dummyHead.next;
};
203. 移除链表元素
203. 移除链表元素原题传送门
「题目描述」
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
「解题思路」
创建一个新链表，遇到相同值的情况，将当前节点的next指向下一个节点的next，否则继续遍历。
var removeElements = 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;
};
24. 两两交换链表中的节点
24. 两两交换链表中的节点原题传送门
「题目描述」
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
「解题思路」
非递归解法
/**
* 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(); // 虚拟节点
hummyHead.next = head;
let p = hummyHead;
let node1,node2; // 当前要交换的两个节点
while((node1 = p.next) && (node2 = p.next.next)){
// 进行交换操作
node1.next = node2.next;
node2.next = node1;
// 将链表串起来
p.next = node2;
p = node1;
}
return hummyHead.next;
};
递归解法
/**
* 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;
};
剑指 Offer 18. 删除链表的节点
剑指 Offer 18. 删除链表的节点原题传送门
「题目描述」
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
「解题思路」
创建一个新链表，遇到相同值的情况，将当前节点的next指向下一个节点的next，否则继续遍历。
/**
* 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;
};
19. 删除链表的倒数第N个节点
19. 删除链表的倒数第N个节点原题传送门
「题目描述」
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
「解题思路」
双指针，先让一个指针q走n 步，然后另一个指针p一起走，当第一个指针q走到尾的时候，此时p指针就指向了我们要删除的节点，进行删除即可。
/**
* 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; // 先让一个指针先走n步
while(q.next){ // 一起走
q = q.next;
p = p.next;
}
p.next = p.next.next; // 找到删除节点，进行删除
return dummyHead.next;
};
142. 环形链表 II
142. 环形链表 II原题传送门
「题目描述」
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以不用额外空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104]内-10^5 <= Node.val <= 10^5pos 的值为 -1 或者链表中的一个有效索引
「解题思路」
两个快慢指针，从头节点出发，如果链表有环，快指针肯定可以在环内和慢指针相遇。没有环就不可能再相遇，相遇必在环内。
相遇时，慢指针走的距离：D+S1D+S1
假设相遇时快指针已经绕环 n 次，它走的距离：D+n(S1+S2)+S1D+n(S1+S2)+S1
因为快指针的速度是 2 倍，所以相同时间走的距离也是 2 倍：
D+n(S1+S2)+S1 = 2(D+S1)
求解得到：「(n-1)S1+ nS2=D」
我们不关心在相遇时快指针已经绕了几次环，我们取 n = 1 ，消掉了 S1：
「D=S2」
那么，当快慢指针第一次相遇时，将快指针放回到头节点，由于 D=s2，那么我们快慢指针一起走，都走1步，它们必定会走到入环点，然后相遇，此时就可返回对应指针下标。
/**
* 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; // 首先，都从头节点出现
while(fast){ // 确保存在环
if(fast.next == null) return null; // fast.next 为null表示无环
low = low.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
if(low == fast){ // 初次相遇
fast = head; // 快指针回到头节点
while(true){
if(fast == low){
return low;
}
fast = fast.next; // 快慢指针一起走
low = low.next;
}
}
}
return null;
};
参考 笨猪爆破组 图解
本文参考
前端该如何准备数据结构和算法？ 写给前端的算法进阶指南，我是如何两个月零基础刷200题 (1.8w字)负重前行，前端工程师如何系统练习数据结构和算法？【上】
结语
❤️关注+点赞+收藏+评论+转发❤️，原创不易，您的支持将会是我最大的动力~
访问超逸の博客，方便小伙伴阅读玩耍~
最后，给看到这里的你拜个年，牛年大吉，好运++，在准备春招の你，能够早点结束春招，offer拿到手软，希望我的文章能够帮助到你，我们很快会在下期相遇~
本文若未经作者授权，禁止转载，如若发现雷同，必将追究责任到底！
【作者：Chocolate】https://juejin.cn/user/2981531267112520/posts
小狮子有话说
你好，我是 Chocolate，一个狮子座的前端攻城狮，希望成为优秀的前端博主，每周都会更新文章，与你一起变优秀~
关注 小狮子前端，回复【小狮子】获取为大家整理好的文章、资源合集我的博客地址： yangchaoyi.vip欢迎收藏，可在博客留言板留下你的足迹，一起交流~觉得文章不错，【 点赞】【在看】支持一波 ✿✿ヽ(°▽°)ノ✿
叮咚~ 可以给小狮子加
星标，便于查找。感谢加入小狮子前端，最好的我们最美的遇见，我们下期再见~