BruceBlogLeetCode Top 100
哈希
1. 两数之和
题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
代码：
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i++) {
const gap = target - nums[i]
if (map.has(nums[i])) {
return [map.get(nums[i]), i]
}
map.set(gap, i)
}
return []
}
49.字母异位词分组
标签：哈希表
题目：
代码：
js
var groupAnagrams = function (strs) {
var map = new Map()
for (var i = 0; i < strs.length; i++) {
var str = strs[i]
// 排序好的字符串作为key
var sortStr = Array.from(str).sort().join('')
if (map.has(sortStr)) {
map.get(sortStr).push(str)
} else {
map.set(sortStr, [str])
}
}
// map.values()返回迭代器，需要转换为数组
return Array.from(map.values())
}
128. 最长连续序列
标签：哈希表、并查集
题目：
代码：
js
var longestConsecutive = function (nums) {
if (nums.length === 0) {
return 0
}
// 先给数组排序
nums.sort((a, b) => a - b)
var count = 1
var max = 1
for (var i = 0; i < nums.length; i++) {
var cur = nums[i]
var next = nums[i + 1]
// 相同元素跳过
if (cur === next) {
continue
}
// 下一个元素比当前元素大1，则计数器加1
if (cur + 1 === next) {
count += 1
} else {
// 重置计数器
count = 1
}
// 更新最大值
max = Math.max(count, max)
}
return max
}
双指针
283.移动零
标签：快慢指针
题目：
代码：
js
// 如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换
// 如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换
var moveZeroes = function (nums) {
var slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] !== 0) {
var tmp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = tmp;
slow += 1;
}
fast += 1;
}
}
11.盛最多水的容器
标签：头尾双指针
题目：
思路：
初始化双指针分别在数组两端，每次循环数值小的一边向内移动一格，并更新最大面积，直到两个指针相遇。
代码：
js
var maxArea = function (height) {
var head = 0, tail = height.length - 1;
var max = 0;
while (head !== tail) {
var h = Math.min(height[head], height[tail]);
var long = tail - head;
max = Math.max(max, h * long);
if (height[head] < height[tail]) head += 1;
else tail -= 1;
}
return max;
}
15. 三数之和
标签：头尾双指针、排序
题目：
代码：
js
var threeSum = function (nums) {
// 先按升序排序
nums.sort((a, b) => a - b);
var res = [];
for (var k = 0;k < nums.length - 2;k++) {
// 如果最小的元素都大于0，直接break，后面的都大于0
if (nums[k] > 0) break;
// 跳过相同的元素组合
if (k > 0 && nums[k] === nums[k - 1]) continue;
var i = k + 1, j = nums.length - 1;
while (i < j) {
var sum = nums[k] + nums[i] + nums[j];
if (sum === 0) {
// 记录组合
res.push([nums[k], nums[i], nums[j]]);
// i和j向内移动，并跳过重复的值，防止记录了重复的结果
while (i < j && nums[i] === nums[++i]);
while (i < j && nums[j] === nums[--j]);
} else if (sum < 0) {
// sum小于0，说明偏小，需要i向内移动，来增大sum
while (i < j && nums[i] === nums[++i]);
} else {
// sum大于0，说明偏大，需要j向内移动，来减小sum
while (i < j && nums[j] === nums[--j]);
}
}
}
return res;
}
42.接雨水
标签：头尾双指针、数组
题目：
主要思路：计算每个位置能接的水的数量，求和。每个位置能接的数量，是左边最高的柱子和右边最高的柱子中较小的那个，减去当前位置的值。
代码：
js
// 方法一：用数组存储前缀和后缀最大值
var trap = function (height) {
var len = height.length;
// 计算出前缀最大值，用数组存储
var preMax = new Array(len);
preMax[0] = height[0];
for (var i = 1;i < len;i++) {
preMax[i] = Math.max(preMax[i - 1], height[i]);
}
// 计算后缀最大值，用数组存储
var sufMax = new Array(len);
sufMax[len - 1] = height[len - 1];
for (var j = len - 2;j > -1;j--) {
sufMax[j] = Math.max(sufMax[j + 1], height[j]);
}
// 每个位置能接的水的数量，为当前位置的前缀和后缀最大值的较小者，减去当前位置的值
var res = 0;
for (var k = 0;k < len;k++) {
res += Math.min(preMax[k], sufMax[k]) - height[k];
}
return res;
}
// 方法二：用头尾双指针优化
var trap = function (height) {
var left = 0, right = height.length - 1;
var leftMax = 0, rightMax = 0;
var res = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
res += leftMax - height[left];
left += 1;
} else {
res += rightMax - height[right];
right -= 1;
}
}
return res;
}
滑动窗口
3. 无重复字符的最长子串
标签：哈希表、左右指针
题目：
代码：
js
var lengthOfLongestSubstring = function (s) {
// map记录每个字符以及目前为止最后一次出现的位置
var map = new Map();
// 注意左指针从 -1 开始
var left = -1;
var res = 0;
for (var right = 0;right < s.length;right++) {
var ch = s[right];
if (map.has(ch)) {
// 更新左指针
left = Math.max(left, map.get(ch));
}
// 记录当前字符以及索引
map.set(ch, right);
// 更新最大长度
res = Math.max(res, right - left);
}
return res;
}
438. 找到字符串中所有字母异位词
标签：双指针、数组、字符串、滑动窗口
题目：
思路：
假设 p 的长度是 n。
定长滑窗：枚举 s 的所有长为 n 的子串 s′，如果 s′ 的每种字母的出现次数，和 p 的每种字母的出现次数都相同，那么 s′ 是 p 的异位词。
代码：
js
// 代码纯享版
var findAnagrams = function (s, p) {
var res = [];
var arrP = new Array(26).fill(0);
var arrS = new Array(26).fill(0);
for (var c of p) {
arrP[c.charCodeAt() - 'a'.charCodeAt()] += 1;
}
for (var right = 0;right < s.length;right++) {
arrS[s[right].charCodeAt() - 'a'.charCodeAt()] += 1;
var left = right - p.length + 1;
if (left < 0) {
continue;
}
if (arrP.join('') === arrS.join('')) {
res.push(left);
}
arrS[s[left].charCodeAt() - 'a'.charCodeAt()] -= 1;
}
return res;
}
// 数组弄长一点，代码简洁一点
var findAnagrams = function(s, p) {
var len = s.length;
// 'z' 的 charCodeAt() 为 122，其实123就可以了，128好看点
var arrS = new Array(128).fill(0);
var arrP = new Array(128).fill(0);
for (var ch of p) {
arrP[ch.charCodeAt()] += 1;
}
var res = [];
for (var right = 0; right < len; right++) {
arrS[s[right].charCodeAt()] += 1;
var left = right - p.length + 1;
if (left < 0) {
continue;
}
if (arrS.toString() === arrP.toString()) {
res.push(left);
}
arrS[s[left].charCodeAt()] -= 1;
}
return res;
}
js
// 详细注释版
var findAnagrams = function (s, p) {
var res = [];
// 统计 p 每种字母出现次数
var arrP = new Array(26).fill(0);
// 统计 s 长为 len(p) 的子串 s' 每种字母的出现次数
var arrS = new Array(26).fill(0);
for (var c of p) {
// charCodeAt() 返回字符的 Unicode 编码值，'a' 的 charCodeAt() 为 97
arrP[c.charCodeAt() - 'a'.charCodeAt()] += 1;
}
for (var right = 0; right < s.length; right++) {
// 开始记录子串 s' 每种字母的出现次数
// 右端点字母进入窗口
arrS[s[right].charCodeAt() - 'a'.charCodeAt()] += 1;
const left = right - p.length + 1;
// 窗口长度不足 len(p)
if (left < 0) {
continue;
}
// s' 和 p 的每种字母的出现次数都相同
if (arrP.join('') === arrS.join('')) {
// 记录子串的起始索引位置
res.push(left);
}
// 左端点字母离开窗口
arrS[s[left].charCodeAt() - 'a'.charCodeAt()] -= 1;
}
return res;
};
子串
560. 和为 K 的子数组
标签：哈希表、前缀和
题目：
代码：
js
// 方法一：双重遍历，时间复杂度O(n^2)
var subarraySum = function (nums, k) {
var count = 0;
for (var i = 0;i < nums.length;i++) {
var sum = 0;
for (var j = i;j < nums.length;j++) {
sum += nums[j];
if (sum === k) {
count += 1;
}
}
}
return count;
}
js
// 方法二：前缀和 + 哈希表，时间复杂度O(n)
var subarraySum = function (nums, k) {
var map = new Map();
map.set(0, 1);
var prefix = 0;
var count = 0;
for (var num of nums) {
prefix += num;
if (map.has(prefix - k)) {
count += map.get(prefix - k);
}
if (map.has(prefix)) {
map.set(prefix, map.get(prefix) + 1);
} else {
map.set(prefix, 1);
}
}
return count;
}
// 使用普通对象代码会更加简洁,但效率没有map高
var subarraySum = function (nums, k) {
var obj = { 0: 1 };
var prefix = 0;
var count = 0;
for (var num of nums) {
prefix += num;
if (obj[prefix - k]) {
count += obj[prefix - k];
}
if (obj[prefix]) {
obj[prefix] += 1;
} else {
obj[prefix] = 1;
}
}
return count;
}
239. 滑动窗口最大值
标签：单调递减队列、数组
题目：
代码：
js
var maxSlidingWindow = function (nums, k) {
if (nums.length === 0 || k === 0) {
return [];
}
var deque = [];
var res = [];
// i、j 分别表示滑动窗口的左右边界
for (var i = 1 - k, j = 0; j < nums.length; i++, j++) {
// 滑动窗口往右移动时，首先删除队列中不存在于窗口中的元素
if (i > 0 && deque[0] === nums[i - 1]) {
deque.shift();
}
// 保证队列的单调递减，将队列中所有小于当前元素的元素删除
while (deque.length > 0 && deque[deque.length - 1] < nums[j]) {
deque.pop();
}
// 将当前元素加入队列
deque.push(nums[j]);
// 当滑动窗口的宽度为 k 时，将当前窗口的最大值加入结果数组
// deque是单调递减队列，第一个元素是最大的
if (i >= 0) {
res.push(deque[0]);
}
}
return res;
}
76. 最小覆盖子串
标签：双指针、数组、字符串、滑动窗口
题目：
代码：
js
var isCovered = function (arrS, arrT) {
// 一定要注意是小于等于 ≤ ！
for (var i = 'A'.charCodeAt(); i <= 'Z'.charCodeAt(); i++) {
if (arrS[i] < arrT[i]) {
return false;
}
}
for (var j = 'a'.charCodeAt(); j <= 'z'.charCodeAt(); j++) {
if (arrS[j] < arrT[j]) {
return false;
}
}
return true;
}
var minWindow = function (s, t) {
var len = s.length;
// 'z'的charCodeAt()为122，所以其实长度123就够用了
var arrS = new Array(128).fill(0);
var arrT = new Array(128).fill(0);
// 记录t中每个字符的出现次数
for (var ch of t) {
arrT[ch.charCodeAt()] += 1;
}
var ansLeft = -1, ansRight = len;
var left = 0;
for (var right = 0; right < len; right++) {
// 右端点字母进入窗口
arrS[s[right].charCodeAt()] += 1;
while (isCovered(arrS, arrT)) {
// 如果找到更短的子串，则更新ansLeft和ansRight
if (right - left < ansRight - ansLeft) {
ansLeft = left;
ansRight = right;
}
// 左端点字母离开窗口
arrS[s[left].charCodeAt()] -= 1;
left += 1;
}
}
return ansLeft < 0 ? '' : s.substring(ansLeft, ansRight + 1);
}
普通数组
53. 最大子数组和
标签：动态规划、数组
题目：
思路：
- 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
- 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
- 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
- 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
代码：
js
var maxSubArray = function (nums) {
var res = nums[0];
// sum 表示当前最大的子数组之和
var sum = 0;
for (var n of nums) {
if (sum > 0) {
sum += n;
} else {
sum = n;
}
res = Math.max(res, sum);
}
return res;
}
56. 合并区间
标签：排序、数组
题目：
思路：
用数组 merged 存储最终的答案。
首先，将列表中的区间按照左端点升序排序。然后将第一个区间加入 merged 数组中，并按顺序依次考虑之后的每个区间：
如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
代码：
js
var merge = function (intervals) {
intervals.sort((a, b) => a[0] - b[0]);
var res = [];
for (var p of intervals) {
var len = res.length;
// 若列表为空，或当前区间和上一个区间不重合，直接添加
if (len <= 0 || p[0] > res[len - 1][1]) {
res.push(p);
} else {
// 区间重合，更新 res 中最后一个区间的右端点
res[len - 1][1] = Math.max(p[1], res[len - 1][1]);
}
}
return res;
}
189. 旋转数组
标签：数组、双指针
题目：
思路：
方法一：使用额外的数组。
可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置，最后将新数组拷贝至原数组即可。
方法二：数组翻转。
该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。
该方法为数组的翻转：首先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，再翻转 [0, (k mod n) − 1] 区间的元素和 [k mod n, n−1] 区间的元素即能得到最后的答案。
代码：
js
// 方法一：使用额外的数组
var rotate = function (nums, k) {
var len = nums.length;
var arr = new Array(len);
for (var i = 0; i < len; i++) {
arr[(i + k) % len] = nums[i];
}
for (var j = 0; j < len; j++) {
nums[j] = arr[j];
}
}
// 方法二：翻转数组
var rotate = function (nums, k) {
var reverse = function (start, end) {
while (start <= end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start += 1;
end -= 1;
}
}
var len = nums.length;
k = k % len;
reverse(0, len - 1);
reverse(0, k - 1);
reverse(k, len - 1);
}
238. 除自身以外数组的乘积
标签：数组、双指针
题目：
思路：
原数组： [1 2 3 4]
左部分的乘积： 1 1 1*2 1*2*3
右部分的乘积： 2*3*4 3*4 4 1
结果： 1*2*3*4 1*3*4 1*2*4 1*2*3*1
当前位置的结果就是它左部分的乘积再乘以它右部分的乘积。因此需要进行两次遍历，第一次遍历用于求左部分的乘积，第二次遍历在求右部分的乘积的同时，再将最后的计算结果一起求出来。
代码：
js
var productExceptSelf = function (nums) {
var len = nums.length;
var res = new Array(len).fill(1);
var left = 0, right = len - 1;
var lp = 1, rp = 1;
while (left < len && right >= 0) {
res[left] *= lp;
res[right] *= rp;
lp *= nums[left++];
rp *= nums[right--];
}
return res;
}
// 使用除法的做法
var productExceptSelf = function(nums) {
var len = nums.length;
var product = 1;
var zeroCount = 0;
var zeroIndex = -1;
for (var k = 0;k < len;k++) {
if (nums[k] !== 0) {
// 计算所有非零元素的乘积
product *= nums[k];
} else {
zeroCount += 1;
zeroIndex = k;
}
}
var res = new Array(len).fill(0);
// 有两个及以上0，结果就都是0
if (zeroCount >= 2) {
return res;
}
// 有1个0，除了0那一位，其它都是0
if (zeroCount === 1) {
res[zeroIndex] = product;
return res;
}
// 没有0，每个位置的值就是所有元素乘积除以自身
for (var i = 0;i < nums.length;i++) {
res[i] = product / nums[i];
}
return res;
}
41. 缺失的第一个正数
标签：哈希表、数组
题目：
思路：
方法二：
实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。
我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：
将数组中所有小于等于 0 的数修改为 N+1；
遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。
方法三：置换
把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。
代码：
js
// 方法一：哈希表，空间复杂度O(n)不满足要求
var firstMissingPositive = function(nums) {
var map = new Map();
for (var n of nums) {
map.set(n, n);
}
var k = 1;
while (true) {
if (!map.has(k)) {
return k;
}
k += 1;
}
}
// 方法二：数组，空间复杂度O(1)
var firstMissingPositive = function(nums) {
var len = nums.length;
// 将数组中所有小于等于 0 的数修改为 N+1
for (var i = 0;i < len;i++) {
if (nums[i] <= 0) {
nums[i] = len + 1;
}
}
for (var j = 0;j < len;j++) {
// 将 |num| - 1 位置的元素添加负号
var num = Math.abs(nums[j]);
if (num <= len) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (var k = 0;k < len;k++) {
if (nums[k] > 0) {
return k + 1;
}
}
return k + 1;
}
// 方法三：置换，空间复杂度O(1)
var firstMissingPositive = function(nums) {
var len = nums.length;
for (var i = 0;i < len;i++) {
// 只需要处理正整数，把x放到下标为x-1的位置
// 注意这里不能用变量接收nums[i]，因为nums[i]的值会改变
while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
var temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
for (var j = 0;j < len;j++) {
if (nums[j] !== j + 1) {
return j + 1;
}
}
return len + 1;
}
矩阵
73. 矩阵置零
标签：标记数组
题目：
思路：
方法一：使用标记数组，空间复杂度为 O(m+n)
用两个标记数组分别记录每一行和每一列是否有0出现。
首先遍历输入数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组，用标记数组更新原数组即可。
方法二：使用两个标记变量，空间复杂度为 O(1)
可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
在实际代码中，首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。
代码：
js
// 方法一：使用标记数组
var setZeroes = function(matrix) {
// m 为行数，n 为列数
var m = matrix.length, n = matrix[0].length;
var row = new Array(m).fill(false);
var col = new Array(n).fill(false);
// 遍历矩阵，记录下0所在的行和列
for (var i = 0;i < m;i++) {
for (var j = 0;j < n;j++) {
if (matrix[i][j] === 0) {
row[i] = col[j] = true;
}
}
}
// 遍历矩阵，更新原矩阵，将0所在行和列的元素置为0
for (var i = 0;i < m;i++) {
for (var j = 0;j < n;j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
// 方法二：使用两个标记变量
var setZeroes = function(matrix) {
var m = matrix.length, n = matrix[0].length;
var rowFlag = false, colFlag = false;
// 记录第一行和第一列是否原本包含 0
for (var j = 0;j < n;j++) {
if (matrix[0][j] === 0) {
rowFlag = true;
}
}
for (var i = 0;i < m;i++) {
if (matrix[i][0] === 0) {
colFlag = true;
}
}
// 从第二行第二列开始遍历，将0所在的行和列记录到第一行和第一列
for (var i = 1;i < m;i++) {
for (var j = 1;j < n;j++) {
if (matrix[i][j] === 0) {
matrix[0][j] = matrix[i][0] = 0;
}
}
}
// 再从第二行第二列开始遍历，根据第一行第一列更新矩阵元素是否为0
for (var i = 1;i < m;i++) {
for (var j = 1;j < n;j++) {
if (matrix[0][j] === 0 || matrix[i][0] === 0) {
matrix[i][j] = 0;
}
}
}
// 根据标记变量更新第一行和第一列
if (rowFlag) {
for (var j = 0;j < n;j++) {
matrix[0][j] = 0;
}
}
if (colFlag) {
for (var i = 0;i < m;i++) {
matrix[i][0] = 0;
}
}
}
链表
160. 相交链表
标签：双指针、哈希表
题目：
代码：
js
var getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) {
return null
}
var a = headA,
b = headB
while (a !== b) {
a = a ? a.next : headB
b = b ? b.next : headA
}
return a
}
206. 反转链表
题目：
标签：双指针、递归
代码：
js
var reverseList = function (head) {
var pre = null,
cur = head
while (cur) {
var tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
}
return pre
}
234. 回文链表
标签：栈、递归
题目：
代码：
js
// 方法一：先用数组记录下链表所有元素，再用双指针判断是否回文
var isPalindrome = function (head) {
var arr = [],
p = head
while (p) {
arr.push(p.val)
p = p.next
}
for (var i = 0, j = arr.length - 1; i < j; i++, j--) {
if (arr[i] !== arr[j]) {
return false
}
}
return true
}
// 方法二：栈存储，再遍历比较弹出
var isPalindrome = function (head) {
var stack = [],
p = head
while (p) {
stack.push(p.val)
p = p.next
}
while (head) {
if (head.val !== stack.pop()) {
return false
}
head = head.next
}
return true
}
// 方法二优化：相当于只需要比较链表前半部分和后半部分即可
var isPalindrome = function (head) {
var stack = [],
p = head
var len = 0
while (p) {
stack.push(p.val)
p = p.next
len++
}
len = len / 2
while (len-- >= 0) {
if (head.val !== stack.pop()) {
return false
}
head = head.next
}
return true
}
// 方法三：递归，难理解
var p = null
var isPalindrome = function (head) {
p = head
return check(head)
}
var check = function (head) {
if (!head) {
return true
}
var res = check(head.next) && p.val === head.val
p = p.next
return res
}
// 帮助理解方法三：逆序打印链表
var printList = function (head) {
if (!head) {
return
}
printList(head.next)
console.log(head.val)
}
141. 环形链表
标签：双指针、哈希表
题目：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true。 否则，返回 false。
代码：
js
// 双指针：快慢指针
var hasCycle = function (head) {
var slow = head,
fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
}
142. 环形链表 II
标签：哈希表、双指针、快慢指针
题目：
代码：
js
// 方法一：遍历链表，哈希表存储每个节点的地址，若哈希表里有重复的地址，则返回该地址，即为环的入口
var detectCycle = function (head) {
var map = new Map()
var p = head
while (p) {
if (map.has(p)) {
return p
}
map.set(p)
p = p.next
}
return p
}
// 方法二：快慢双指针。
// 首先快慢指针找到第一次重合的节点，接着快指针从头开始，两个指针相遇的节点即为环的入口
var detectCycle = function (head) {
var slow = head,
fast = head
while (true) {
// 没有环，返回null
if (!fast || !fast.next) {
return null
}
slow = slow.next
fast = fast.next.next
// 找到重合的第一个节点
if (slow === fast) {
break
}
}
// 快指针返回头节点
fast = head
while (slow !== fast) {
slow = slow.next
fast = fast.next
}
return slow
}
21. 合并两个有序链表
标签：递归、双指针
题目：
代码：
js
// 方法一：遍历链表存到数组，排好序，返回一个新链表
var mergeTwoLists = function (l1, l2) {
if (!l1 && !l2) {
return null
}
var arr = []
while (l1) {
arr.push(l1.val)
l1 = l1.next
}
while (l2) {
arr.push(l2.val)
l2 = l2.next
}
arr.sort((a, b) => a - b)
var head = new ListNode(),
p = head
for (var i = 0; i < arr.length; i++) {
p.val = arr[i]
if (i < arr.length - 1) {
p.next = new ListNode()
p = p.next
}
}
return head
}
// 方法二：快慢链表
var mergeTwoLists = function (l1, l2) {
var head = new ListNode(),
p = head
while (l1 && l2) {
if (l1.val <= l2.val) {
p.next = l1
l1 = l1.next
} else {
p.next = l2
l2 = l2.next
}
p = p.next
}
p.next = l1 || l2
return head.next
}
2. 两数相加
标签：链表、pre 指针
题目：
代码：
js
var addTwoNumbers = function (l1, l2) {
var pre = new ListNode(0)
var cur = pre
// 进位
var carry = 0
while (l1 || l2) {
var a = l1 ? l1.val : 0
var b = l2 ? l2.val : 0
// 求和
var sum = a + b + carry
// 注意此处要向下取整，计算进位
carry = Math.floor(sum / 10)
// 取余数
sum = sum % 10
cur.next = new ListNode(sum)
cur = cur.next
if (l1) {
l1 = l1.next
}
if (l2) {
l2 = l2.next
}
}
if (carry > 0) {
cur.next = new ListNode(carry)
}
return pre.next
}
19. 删除链表的倒数第 N 个结点
标签：pre 指针、双指针
题目：
代码：
js
// 思路：快指针先移动 n 步，接着两个指针共同移动，直到快指针到尾部，此时慢指针刚到到达被删除节点的前一个节点
var removeNthFromEnd = function (head, n) {
// 技巧：好用的 pre 指针
var pre = new ListNode()
pre.next = head
// 初始化快慢指针为 pre 指针
var slow = pre,
fast = pre
// fast 先移动 n 步
while (n > 0) {
fast = fast.next
n -= 1
}
// 快慢指针一起向前移动，直到快指针到末尾
while (fast.next) {
slow = slow.next
fast = fast.next
}
// 删除节点
slow.next = slow.next.next
// 返回 pre.next，head 可能被删除
return pre.next
}
24. 两两交换链表中的节点
标签：递归、迭代、pre 指针
题目：
代码：
js
// 方法一：递归
var swapPairs = function (head) {
// 终止条件：当前无节点或只有一个节点，无法交换
if (!head || !head.next) {
return head
}
// 递归调用单元：head 连接后面完成交换的子链表，next 连接 head，完成交换
var temp = head.next
head.next = swapPairs(temp.next)
temp.next = head
// 返回值：完成交换的子链表
return temp
}
// 方法二：迭代
var swapPairs = function (head) {
var pre = new ListNode()
pre.next = head
var p = pre
while (p.next && p.next.next) {
var start = p.next
var end = p.next.next
start.next = end.next
end.next = start
p.next = end
p = start
}
return pre.next
}
25. K 个一组翻转链表
标签：dummy 指针
题目：
代码：
js
// 反转链表
var reverse = function (head) {
var pre = null,
cur = head
while (cur) {
var temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
}
var reverseKGroup = function (head, k) {
var dummy = new ListNode()
dummy.next = head
var p = dummy
var tail = dummy
while (p.next) {
// 找到要反转的K链表的头尾节点
var start = p.next
for (var i = 0; i < k; i++) {
tail = tail.next
// 如果不够k个节点，则直接返回
if (!tail) {
return dummy.next
}
}
// 记录下尾节点下一个节点
var next = tail.next
// 先断开链表，否则后面一整条链表都会进行反转
tail.next = null
p.next = reverse(start)
// 反转之后，start就变成尾节点
start.next = next
// 进行下一组的初始化
p = start
tail = p
}
return dummy.next
}
138. 随机链表的复制
标签：哈希表
题目：
代码：
js
var copyRandomList = function (head) {
if (!head) {
return null
}
var map = new Map()
var cur = head
// 遍历链表，建立原链表节点和新链表节点的对应关系
while (cur) {
map.set(cur, new Node(cur.val))
cur = cur.next
}
cur = head
// 遍历链表，构建新链表节点的next指针和random指针
while (cur) {
// 链表尾节点的 next 必须指向 null，否则会报错
map.get(cur).next = map.get(cur.next) || null
map.get(cur).random = map.get(cur.random)
cur = cur.next
}
return map.get(head)
}
148. 排序链表
标签：排序
题目：
代码：
js
// 最简单的方法，用数组接收，排序，再生成链表
var sortList = function (head) {
var arr = []
while (head) {
arr.push(head.val)
head = head.next
}
arr.sort((a, b) => a - b)
var dummy = new ListNode()
var pre = dummy
for (var i = 0; i < arr.length; i++) {
var node = new ListNode(arr[i])
pre.next = node
pre = node
}
return dummy.next
}
23. 合并 K 个排序链表
标签：归并排序
题目：
代码：
js
// 最简单的方法，遍历，用数组接收所有节点值，排序，再生成链表
var mergeKLists = function (lists) {
var arr = []
for (var i = 0; i < lists.length; i++) {
var head = lists[i]
while (head) {
arr.push(head.val)
head = head.next
}
}
arr.sort((a, b) => a - b)
var dummy = new ListNode()
var pre = dummy
for (var j = 0; j < arr.length; j++) {
var node = new ListNode(arr[j])
pre.next = node
pre = node
}
return dummy.next
}
二叉树
94.二叉树的中序遍历
标签：深度优先搜索、递归
题目：
代码：
js
var inorderTraversal = function (root) {
var res = []
inorder(root, res)
return res
}
var inorder = function (root, res) {
if (!root) {
return
}
inorder(root.left, res)
res.push(root.val)
inorder(root.right, res)
}
图论
回溯
二分查找
35.搜索插入位置
标签：二分查找
题目：
代码：
js
var searchInsert = function (nums, target) {
var len = nums.length
if (nums[len - 1] < target) {
return len
}
var left = 0,
right = len - 1
while (left < right) {
// 除以 2 向下取整
var mid = (left + right) >> 1
if (nums[mid] === target) {
return mid
} else if (nums[mid] < target) {
// 注意 left 要加 1，不然向下取整可能会导致死循环
left = mid + 1
} else {
right = mid
}
}
return left
}