之前的文章大部分都是寫給女友系列，但有一段時間沒有進行更新了，一方面春招要準備開始了，另一方面女友還在準備年前面試，面試之後的復盤總結是挺重要的。
訪問 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<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
};
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<S.length;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<T.length;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<A.length;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.length;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<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()
};
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<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('')
};
隊列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. 反轉鍊表 II92. 反轉鍊表 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. 環形鍊表 II142. 環形鍊表 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
解釋：鍊表中沒有環。提示：
-10^5 <= Node.val <= 10^5「解題思路」
兩個快慢指針，從頭節點出發，如果鍊表有環，快指針肯定可以在環內和慢指針相遇。沒有環就不可能再相遇，相遇必在環內。
相遇時，慢指針走的距離：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