前端码农

Appearance

leetCode 刷题解析 ​

704.二分查找 ​

js
/**
 * 二分查找（左闭右闭区间）
 * @param {number[]} nums - 升序排列的整数数组
 * @param {number} target - 目标值
 * @return {number} 目标值在数组中的索引，如果不存在则返回-1
 */
var search = function (nums, target) {
  let left = 0; // 左边界
  let right = nums.length - 1; // 右边界（包含）

  // 当左边界小于等于右边界时继续查找（区间有效）
  while (left <= right) {
    // 计算中间位置（使用位运算代替除法以提高性能）
    let m = (left + right) >> 1;

    if (nums[m] > target) {
      // 中间值大于目标值，在左半部分继续查找
      right = m - 1; // 调整右边界（m已检查，故排除）
    } else if (nums[m] < target) {
      // 中间值小于目标值，在右半部分继续查找
      left = m + 1; // 调整左边界（m已检查，故排除）
    } else {
      // 找到目标值，返回索引
      return m;
    }
  }

  // 未找到目标值
  return -1;
};

27.原地移除数组元素 ​

示例 ​

  • target=5,[1,3,5,3,5] -> [1,3,3] 输入长度 3
js
/**
 * 双指针：快慢指针法
 * @param {number[]} nums - 待处理的数组
 * @param {number} val - 需要移除的值
 * @return {number} 移除后数组的新长度
 */
var removeElement = function (nums, val) {
  let slow = 0; // 慢指针：指向下一个有效元素的位置

  // 快指针遍历整个数组
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      // 当前元素不是要移除的值，将其复制到慢指针位置
      nums[slow] = nums[fast];
      slow++; // 慢指针向前移动
    }
    // 如果要移除的值，快指针继续前进，慢指针保持不动
  }

  return slow; // 返回新数组的长度
};

977.有序数组的平方 ​

示例 ​

  • [-4,1,2,3] 平方后排序-> [1,4,9,16]
js
/**
 * 双指针：从两端向中间遍历
 * @param {number[]} nums - 非递减排序的整数数组（可能包含负数）
 * @return {number[]} 平方后的有序数组
 */
var sortedSquares = function (nums) {
  let k = nums.length - 1; // 结果数组的填充位置（从后往前）
  let left = 0; // 左指针
  let right = nums.length - 1; // 右指针
  let result = new Array(nums.length); // 预分配结果数组

  while (left <= right) {
    // 计算左右指针指向元素的平方
    let leftSquare = nums[left] * nums[left];
    let rightSquare = nums[right] * nums[right];

    if (leftSquare > rightSquare) {
      result[k--] = leftSquare; // 左边平方较大，放入结果末尾
      left++; // 左指针右移
    } else {
      result[k--] = rightSquare; // 右边平方较大或相等，放入结果末尾
      right--; // 右指针左移
    }
  }
  return result;
};

209.长度最小的字串 ​

示例 ​

  • 子数组只和大于或者等于 target 最小长度 2
  • target=10, [1,5,5] -> [5,5] 输出最小长度 2
js
/**
 * 滑动窗口算法：寻找和至少为target的最短连续子数组
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 *
 */
var minSubArrayLen = function (target, nums) {
  let left = 0; // 窗口左边界指针
  let sum = 0; // 当前窗口内元素的和
  let result = Infinity; // 最小子数组长度，初始设为无穷大便于比较

  // 右指针遍历数组，扩展窗口
  for (let right = 0; right < nums.length; right++) {
    // 将右指针指向的元素加入窗口和
    sum += nums[right];

    // 关键：当窗口和满足条件时，使用while循环持续收缩左边界
    // 使用while而不是if的原因：可能需要多次收缩才能找到当前右边界下的最小窗口
    // 示例：target=10, nums=[1,5,5]
    // - 第一次收缩：窗口[1,5,5] 1+5+5>=10，长度3
    // - 第二次检查：[5,5]仍然满足5+5>=10，长度2,继续收缩找到真正的最小窗口
    while (sum >= target) {
      // 更新最小长度：取当前窗口长度与历史最小值的较小者
      result = Math.min(result, right - left + 1);
      // 收缩左边界：从窗口和中减去左边界元素，左指针右移
      sum -= nums[left++];
    }
  }

  // 如果找到满足条件的子数组返回其长度，否则返回0
  return result === Infinity ? 0 : result;
};

203.移除链表元素 ​

示例 ​

  • target=3,[1 -> 2 -> 3 >5 -> 2] -> [1 -> 2 -> 5 -> 2]
js
/**

@param {ListNode} head

@param {number} val

@return {ListNode}
*/
var removeElements = function (head, val) {
  // 创建虚拟头节点，简化删除真实头节点的特殊情况处理
  let dummy = {
    next: head,
  };
  let current = dummy;

  // 遍历链表，检查每个节点的下一个节点
  while (current.next) {
    if (current.next.val === val) {
      // 跳过值等于val的节点（移除该节点）
      current.next = current.next.next;
    } else {
      // 移动到下一个节点继续检查
      current = current.next;
    }
  }

  // 返回处理后的链表头节点
  return dummy.next;
};

206.反转链表 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let pre = null; // 前驱节点，初始为null
  let cur = head; // 当前节点，从头节点开始
  // 遍历链表直到当前节点为null
  while (cur) {
    // 保存下一个节点，防止断链
    let next = cur.next;
    // 反转指针：当前节点指向前驱节点
    cur.next = pre;
    // 移动指针：前驱节点和当前节点都前进一位
    pre = cur;
    cur = next;
  }
  return pre;
};

24.两两交换链表中相邻的节点 ​

示例 ​

  • [1 -> 2 -> 3 >4] -> [2 -> 1 -> 4 >3]
js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  // 处理空链表的情况
  if (head == null) return head;

  // 创建虚拟头节点，简化边界条件处理
  // dummy节点的next指向原始链表的头节点
  let dummy = {
    next: head,
  };

  // cur指针用于遍历链表，初始指向dummy节点
  let cur = dummy;

  // 当存在两个连续的节点可以交换时进入循环
  while (cur.next && cur.next.next) {
    // 保存需要交换的节点引用：

    // temp1: 第一个需要交换的节点
    let temp1 = cur.next;
    // temp2: 交换后第一个节点应该连接的下一个节点
    // (即下一对节点的开始位置)
    let temp2 = cur.next.next.next;

    // 执行交换操作：
    // 1. 将cur的next指向第二个节点
    cur.next = cur.next.next;
    // 2. 将第二个节点的next指向第一个节点（完成交换）
    cur.next.next = temp1;
    // 3. 将交换后的第二个节点（原第一个节点）连接到下一对节点
    temp1.next = temp2;

    // 移动cur指针到交换后的第二个节点位置
    // 为下一对交换做准备
    cur = temp1;
  }

  // 返回交换后的链表头节点（dummy.next）
  return dummy.next;
};

19.删除链表的倒数第 N 个节点 ​

示例 ​

  • target=2,[1 -> 2 -> 3 ->4] -> [1 -> 2 -> 4]
js
/**
 * 双指针：快慢指针
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  // 创建虚拟头节点，简化删除头节点的处理
  let dummy = {
    next: head,
  };

  // 慢指针
  let slow = dummy;
  // 快指针
  let fast = dummy;

  // 快指针先移动 n+1 步，创造与慢指针的 n+1 间隔
  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  // 同时移动快慢指针，直到快指针到达末尾
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }

  // 删除慢指针的下一个节点（倒数第 n 个）
  slow.next = slow.next.next;

  return dummy.next; // 返回真实头节点
};

141.环形链表 ​

js
/**
 * 使用快慢指针算法检测链表中是否存在环。
 * 快指针每次移动两步，慢指针每次移动一步。如果存在环，快指针最终会与慢指针相遇。
 * @param {ListNode} head - 链表的头节点
 * @return {boolean} 如果链表中存在环返回 true，否则返回 false
 */
var hasCycle = function (head) {
  let slow = head; // 慢指针，每次移动一步
  let fast = head; // 快指针，每次移动两步

  // 当快指针及其下一节点均存在时继续遍历
  while (fast && fast.next) {
    slow = slow.next; // 慢指针移动一步
    fast = fast.next.next; // 快指针移动两步

    // 如果快慢指针相遇，说明存在环
    if (slow === fast) {
      return true;
    }
  }

  // 快指针到达链表末尾，无环
  return false;
};

142.环形链表 2 ​

js
/**
 * 使用快慢指针算法检测链表中的环并返回环的起始节点。
 * 算法分为两个阶段：
 * 1. 检测环：快指针每次移动两步，慢指针每次移动一步，如果存在环，它们最终会相遇
 * 2. 寻找环起点：当快慢指针相遇后，将一个指针重置到链表头部，然后两个指针以相同速度移动，
 *    它们再次相遇的节点就是环的起始节点
 * @param {ListNode} head - 链表的头节点
 * @return {ListNode} 如果存在环，返回环的起始节点；否则返回null
 */
var detectCycle = function (head) {
  let slow = head; // 慢指针，每次移动一步
  let fast = head; // 快指针，每次移动两步

  // 第一阶段：检测链表中是否存在环
  while (fast && fast.next) {
    slow = slow.next; // 慢指针移动一步
    fast = fast.next.next; // 快指针移动两步

    // 如果快慢指针相遇，说明链表中存在环
    if (slow === fast) {
      // 第二阶段：寻找环的起始节点
      let index1 = head; // 从链表头部开始
      let index2 = fast; // 从相遇点开始

      // 两个指针以相同速度移动，直到它们相遇
      while (index1 !== index2) {
        index1 = index1.next;
        index2 = index2.next;
      }

      // 相遇点即为环的起始节点
      return index1;
    }
  }

  // 快指针到达链表末尾，说明链表中无环
  return null;
};

242.有效的字母异位词 ​

示例 ​

  • 相同的字母组成，顺序可以不一样
  • s = "anagram", t = "nagaram" -> true
  • s = "rat", t = "car" -> false
js
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  // 长度不同直接返回false
  if (s.length !== t.length) return false;

  // 创建26个字母的计数数组，初始值为0
  let arr = new Array(26).fill(0);

  // 获取字母'a'的ASCII码值作为基准
  let base = "a".charCodeAt(); // 'a' = 97

  // 遍历字符串s，统计每个字母出现的次数
  for (let i = 0; i < s.length; i++) {
    // 计算当前字母在数组中的索引位置（0-25）
    let index = s[i].charCodeAt() - base;
    arr[index]++; // 对应字母计数加1
  }

  // 遍历字符串t，减少每个字母的计数
  for (let i = 0; i < t.length; i++) {
    let index = t[i].charCodeAt() - base;
    arr[index]--; // 对应字母计数减1
  }

  // 检查计数数组，所有元素都应为0
  for (let i = 0; i < arr.length; i++) {
    // 任何一个位置不为0，说明两个字符串不是字母异位词
    if (arr[i] !== 0) {
      return false;
    }
  }

  // 所有字母计数都匹配，返回true
  return true;
};

150.逆波兰表示式求值 ​

js
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  // 使用栈来存储操作数
  let stack = [];

  // 使用策略模式定义运算符对应的计算函数
  let strategy = {
    "+": (a, b) => a + b, // 加法运算
    "-": (a, b) => a - b, // 减法运算
    "*": (a, b) => a * b, // 乘法运算
    "/": (a, b) => parseInt(a / b), // 除法运算（向零取整）
  };

  // 遍历逆波兰表达式中的所有token
  for (let i = 0; i < tokens.length; i++) {
    let token = tokens[i];

    // 如果当前token是运算符
    if (token in strategy) {
      // 从栈中弹出两个操作数（注意顺序：先弹出的是右操作数）
      let b = stack.pop();
      let a = stack.pop();
      // 执行运算并将结果压入栈中
      stack.push(strategy[token](a, b));
    } else {
      // 如果是操作数，转换为数字后压入栈中
      stack.push(+token);
    }
  }

  // 栈中最后剩下的元素就是最终计算结果
  return stack.pop();
};

349.两个数组的交集 ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 使用Set数据结构对两个数组进行去重
  // Set自动去除重复元素，提高查找效率
  let set1 = new Set(nums1);
  let set2 = new Set(nums2);

  // 存储交集结果的数组
  let result = [];

  // 遍历第一个集合中的元素
  for (let v of set1) {
    // 检查当前元素是否也存在于第二个集合中
    if (set2.has(v)) {
      // 如果存在，说明是交集元素，加入结果数组
      result.push(v);
    }
  }

  // 返回两个数组的交集结果（已去重）
  return result;
};

1.两数之合 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 创建哈希表，用于存储数字和对应的索引
  // key: 数字值, value: 数组索引
  let map = new Map();

  // 遍历数组中的每个元素
  for (let i = 0; i < nums.length; i++) {
    let n = nums[i]; // 当前数字
    let diff = target - n; // 计算需要的互补值

    // 检查哈希表中是否存在需要的互补值
    if (map.has(diff)) {
      // 如果存在，返回互补值的索引和当前索引
      return [map.get(diff), i];
    } else {
      // 如果不存在，将当前数字和索引存入哈希表
      map.set(n, i);
    }
  }
};

454.四数相加 2 ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (nums1, nums2, nums3, nums4) {
  // 创建哈希表，用于存储前两个数组元素和的出现次数
  // key: nums1[i] + nums2[j] 的和
  // value: 该和出现的次数
  let countMap = new Map();
  let result = 0;

  // 第一组：计算nums1和nums2中所有元素的两两之和
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      let key = nums1[i] + nums2[j]; // 计算两数之和
      let count = countMap.get(key) || 0; // 获取当前和的计数（默认为0）
      countMap.set(key, count + 1); // 更新哈希表中的计数
    }
  }

  // 第二组：计算nums3和nums4中所有元素的两两之和
  // 并在哈希表中查找能够使四数之和为0的互补值
  for (let i = 0; i < nums3.length; i++) {
    for (let j = 0; j < nums4.length; j++) {
      let key = nums3[i] + nums4[j]; // 计算后两个数组的两数之和
      // 查找哈希表中是否存在互补值（使总和为0）
      if (countMap.has(-key)) {
        let count = countMap.get(-key); // 获取互补值的出现次数
        result += count; // 累加到结果中
      }
    }
  }

  return result;
};

15.三数之和 ​

js
/**
 * 双指针法：头尾收缩
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // 边界情况处理：如果数组长度小于3，直接返回空数组
  if (nums.length < 3) return [];

  // 对数组进行排序（从小到大），这是双指针法的前提
  nums.sort((a, b) => a - b);

  // 结果收集数组
  let result = [];

  // 遍历数组，i为第一个数的索引
  for (let i = 0; i < nums.length - 2; i++) {
    // 跳过重复的i值：如果当前元素与前一个相同，跳过以避免重复解
    if (nums[i] === nums[i - 1]) {
      continue;
    }

    // 定义左右指针：left从i+1开始，right从末尾开始
    let left = i + 1;
    let right = nums.length - 1;

    // 双指针向中间收缩，寻找满足条件的三元组
    while (left < right) {
      // 计算当前三个数的和
      let sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        // 找到满足条件的三元组，加入结果集
        result.push([nums[i], nums[left], nums[right]]);

        // 跳过左侧重复元素：移动left指针直到遇到不同的值
        while (nums[left] === nums[left + 1]) {
          left++;
        }
        // 跳过右侧重复元素：移动right指针直到遇到不同的值
        while (nums[right] === nums[right - 1]) {
          right--;
        }

        // 移动左右指针继续寻找下一个可能的解
        left++;
        right--;
      } else if (sum > 0) {
        // 和太大：需要减小和，移动右指针（因为数组已排序）
        right--;
      } else {
        // 和太小：需要增大和，移动左指针（因为数组已排序）
        left++;
      }
    }
  }

  return result;
};

18.四数之和 ​

js
/**
 * 双指针法：头尾收缩+三数之和
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  // 处理边界情况：数组长度小于4时直接返回空数组
  if (nums.length < 4) return [];

  let result = [];
  // 先将数组排序，便于使用双指针法和去重
  nums.sort((a, b) => a - b);

  // 第一层循环：固定第一个数
  for (let i = 0; i < nums.length; i++) {
    // 提前终止条件：如果当前数已经大于目标值且为非负数
    // 由于数组已排序，后面的数只会更大，不可能再找到解
    if (nums[i] > target && nums[i] >= 0) {
      break;
    }
    // 去重：跳过与上一个相同的数字，避免重复解
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    // 第二层循环：固定第二个数
    for (let j = i + 1; j < nums.length; j++) {
      // 提前终止条件：前两个数之和已经大于目标值且为非负
      if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
        break;
      }
      // 去重：跳过与上一个相同的数字
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }

      // 使用双指针法寻找剩余两个数
      let left = j + 1; // 左指针：从j+1开始
      let right = nums.length - 1; // 右指针：从数组末尾开始

      while (left < right) {
        // 计算四数之和
        let sum = nums[i] + nums[j] + nums[left] + nums[right];

        if (sum === target) {
          // 找到满足条件的四元组
          result.push([nums[i], nums[j], nums[left], nums[right]]);

          // 去重：跳过左侧相同的数字
          while (left < right && nums[left] === nums[left + 1]) {
            left++;
          }
          // 去重：跳过右侧相同的数字
          while (left < right && nums[right] === nums[right - 1]) {
            right--;
          }
          // 移动双指针继续寻找
          left++;
          right--;
        } else if (sum > target) {
          // 和太大，需要减小，移动右指针
          right--;
        } else {
          // 和太小，需要增大，移动左指针
          left++;
        }
      }
    }
  }
  return result;
};

344.反转字符串 ​

js
/**
 * 双指针：头尾互换
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    let t = s[right];
    s[right] = s[left];
    s[left] = t;
    left++;
    right--;
  }
  return s;
};

541.反转字符串 2 ​

js
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function (s, k) {
  // 将字符串转换为数组，便于进行字符交换操作
  let result = s.split("");
  let len = result.length;

  // 以2k为步长遍历字符串
  for (let i = 0; i < len; i += 2 * k) {
    // 计算反转区间的起始位置
    let left = i;
    // 计算反转区间的结束位置（注意边界处理）
    let right = left + k > len ? len : left + k;

    // 反转前k个字符（或剩余字符）
    reverse(left, right - 1, result);
  }

  // 将字符数组重新组合成字符串返回
  return result.join("");
};

/**
 * 使用双指针法反转字符数组中指定区间的字符
 * @param {number} left - 反转区间的起始索引
 * @param {number} right - 反转区间的结束索引
 * @param {string[]} arr - 字符数组
 */
function reverse(left, right, arr) {
  // 使用双指针从两端向中间交换字符
  while (left < right) {
    // 交换左右指针指向的字符
    let temp = arr[right];
    arr[right] = arr[left];
    arr[left] = temp;

    // 移动指针继续交换
    left++;
    right--;
  }
}

151.反转字符串中的单词 ​

js
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  // 将输入字符串按空格分割成单词数组
  // 注意：连续多个空格会产生空字符串元素
  let result = s.split(" ");

  // 创建新数组用于存储反转后且过滤掉空字符串的单词
  let arr = [];

  // 从后往前遍历原单词数组（实现单词顺序反转）
  for (let i = result.length - 1; i >= 0; i--) {
    // 过滤掉空字符串（由连续空格产生）
    if (result[i] != "") {
      // 将非空单词添加到新数组中
      arr.push(result[i]);
    }
  }

  // 将新数组中的单词用单个空格连接成字符串返回
  return arr.join(" ");
};

459.重复的子字符串 ​

js
/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function (s) {
  // 将原字符串拼接成双倍字符串
  const doubled = s + s;

  // 去掉双倍字符串的首尾字符（即从第1个字符开始到倒数第2个字符）
  const trimmed = doubled.slice(1, -1);

  // 检查原字符串是否出现在处理后的双倍字符串中
  // 如果存在，说明原字符串可以由某个子串重复多次构成
  return trimmed.includes(s);
};

232.用栈实现队列 ​

js
/**
 * 使用双栈实现队列
 * 队列的特性：先进先出 (FIFO)
 * 栈的特性：后进先出 (LIFO)
 */
var MyQueue = function () {
  this.intStack = []; // 输入栈：用于接收 push 操作的元素
  this.outStack = []; // 输出栈：用于处理 pop 和 peek 操作
};

/**
 * 内部方法：确保输出栈中有元素可供操作
 * 当输出栈为空时，将输入栈的所有元素转移到输出栈
 * 这样可以将输入栈中的元素顺序反转，符合队列的先进先出特性
 */
MyQueue.prototype.intOutStack = function () {
  if (this.outStack.length === 0) {
    if (this.intStack.length > 0) {
      while (this.intStack.length > 0) {
        this.outStack.push(this.intStack.pop());
      }
    }
  }
};

/**
 * 向队列尾部添加元素
 * @param {number} x - 要添加的元素
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.intStack.push(x); // 直接将元素压入输入栈
};

/**
 * 移除并返回队列头部的元素
 * @return {number} - 队列头部的元素
 */
MyQueue.prototype.pop = function () {
  this.intOutStack(); // 确保输出栈中有元素
  return this.outStack.pop(); // 从输出栈弹出元素（即队列头部）
};

/**
 * 返回队列头部的元素（不移除）
 * @return {number} - 队列头部的元素
 */
MyQueue.prototype.peek = function () {
  this.intOutStack(); // 确保输出栈中有元素
  return this.outStack[this.outStack.length - 1]; // 查看输出栈顶部元素（即队列头部）
};

/**
 * 检查队列是否为空
 * @return {boolean} - 如果队列为空返回 true，否则返回 false
 */
MyQueue.prototype.empty = function () {
  return this.intStack.length === 0 && this.outStack.length === 0;
};

225.用队列实现栈 ​

js
var MyStack = function () {
  this.q = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
  this.q.push(x);
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
  return this.q.pop();
};

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
  return this.q[this.q.length - 1];
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
  return this.q.length === 0;
};

20.有效括号 ​

js
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 如果字符串长度为奇数，直接返回false，因为括号必须成对出现
  if (s.length % 2 !== 0) return false;

  // 使用栈数据结构来跟踪未匹配的左括号
  let stack = [];

  // 使用映射表来定义括号的匹配关系
  let map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  // 遍历字符串中的每个字符
  for (let i = 0; i < s.length; i++) {
    let char = s[i];

    // 如果是左括号，压入栈中
    if (char === "(" || char === "{" || char === "[") {
      stack.push(char);
    } else {
      // 如果是右括号，检查栈顶元素是否与之匹配
      if (stack.length > 0) {
        // 弹出栈顶元素并检查是否匹配
        if (map[stack.pop()] !== char) {
          return false; // 不匹配则返回false
        }
      } else {
        // 栈为空但遇到了右括号，说明有额外的右括号
        return false;
      }
    }
  }

  // 最后检查栈是否为空，空栈表示所有括号都正确匹配
  return stack.length === 0;
};

1047.删除字符串中的所有相邻重复项 ​

js
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  // 使用栈来存储字符，便于检测和消除相邻重复项
  let stack = [];

  // 遍历字符串中的每个字符
  for (let i = 0; i < s.length; i++) {
    let currentChar = s[i];

    // 检查栈是否为空
    if (stack.length > 0) {
      // 弹出栈顶元素进行比较
      let topChar = stack.pop();

      // 如果栈顶字符与当前字符不同，则重新压入栈顶字符和当前字符
      if (topChar !== currentChar) {
        stack.push(topChar);
        stack.push(currentChar);
      }
      // 如果相同，则不进行任何操作（相当于消除了这两个相同的字符）
    } else {
      // 栈为空时，直接将当前字符压入栈
      stack.push(currentChar);
    }
  }

  // 将栈中剩余的字符连接成字符串返回
  return stack.join("");
};

239.滑动窗口最大值 ​

js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 单调队列类：维护一个递减队列，队首始终是当前窗口的最大值
  function MonotonicQueue() {
    this.queue = []; // 存储元素的递减队列

    // 向队列中添加元素，保持队列的单调递减性
    this.enqueue = function (value) {
      // 移除队列尾部所有小于当前值的元素
      while (
        this.queue.length > 0 &&
        this.queue[this.queue.length - 1] < value
      ) {
        this.queue.pop();
      }
      // 将当前值添加到队列尾部
      this.queue.push(value);
    };

    // 从队列中移除元素（只有当要移除的元素是当前最大值时才移除）
    this.dequeue = function (value) {
      // 如果要移除的值等于队列首部的值（当前最大值），则移除
      if (this.queue.length > 0 && value === this.queue[0]) {
        this.queue.shift();
      }
    };

    // 获取当前队列中的最大值（即队列首部元素）
    this.getMax = function () {
      return this.queue[0];
    };
  }

  let monoQueue = new MonotonicQueue(); // 创建单调队列实例
  let left = 0; // 窗口左边界
  let right = 0; // 窗口右边界
  let result = []; // 存储每个窗口的最大值

  // 初始化第一个窗口
  while (right < k) {
    monoQueue.enqueue(nums[right]);
    right++;
  }
  result.push(monoQueue.getMax()); // 记录第一个窗口的最大值

  // 滑动窗口处理剩余元素
  while (right < nums.length) {
    // 新元素进入窗口
    monoQueue.enqueue(nums[right]);
    // 旧元素离开窗口
    monoQueue.dequeue(nums[left]);
    // 记录当前窗口的最大值
    result.push(monoQueue.getMax());

    // 移动窗口
    right++;
    left++;
  }

  return result;
};

144.二叉树的前序遍历 ​

js
/**
 * 深度优先遍历（递归实现）
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  let result = [];
  let dfs = (tree) => {
    // 如果当前节点为空，直接返回
    if (tree === null) return;
    // 将当前节点的值添加到结果数组中
    // 中节点的位置
    result.push(tree.val);
    // 递归遍历左子树
    dfs(tree.left);
    // 递归遍历右子树
    dfs(tree.right);
  };
  dfs(root);
  return result;
};

145.二叉树的后序遍历 ​

js
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  let result = [];
  let dfs = (tree) => {
    if (tree === null) return;
    dfs(tree.left);
    dfs(tree.right);
    result.push(tree.val);
  };
  dfs(root);
  return result;
};

94.二叉树的中序遍历 ​

js
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let result = [];
  let dfs = (tree) => {
    if (tree === null) return;
    dfs(tree.left);
    result.push(tree.val);
    dfs(tree.right);
  };
  dfs(root);
  return result;
};

102.二叉树的层序遍历 ​

js
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  // 处理空树情况
  if (root === null) return [];

  // 使用队列进行层序遍历（先进先出）
  let queue = [root];
  let result = [];

  while (queue.length > 0) {
    // 记录当前层的节点数量
    let size = queue.length;
    let currentLevelNodes = []; // 存储当前层所有节点的值

    // 遍历当前层的所有节点
    while (size--) {
      // 从队列头部取出节点（先进先出）
      let node = queue.shift();
      currentLevelNodes.push(node.val);

      // 将当前节点的左右子节点加入队列尾部（下一层的节点）
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }

    // 将当前层的结果加入最终结果数组
    result.push(currentLevelNodes);
  }

  return result;
};

226.反转二叉树 ​

js
/**
 * 翻转二叉树 - 深度优先搜索（前序遍历）实现
 *
 * @param {TreeNode}
 * @return {TreeNode}
 */
var invertTree = function (root) {
  // 交换节点的左右子树
  const swap = (node) => {
    const temp = node.left;
    node.left = node.right;
    node.right = temp;
  };

  // 深度优先遍历函数
  const dfs = (node) => {
    // 递归终止条件：当前节点为空
    if (node === null) return;
    // 前序遍历：先处理当前节点，交换左右子树
    swap(node);
    // 递归处理左子树
    dfs(node.left);
    // 递归处理右子树
    dfs(node.right);
  };
  dfs(root);
  return root;
};

101.对称二叉树 ​

js
/**
 * 判断二叉树是否对称 - 递归实现
 *
 * @param {TreeNode} root - 二叉树的根节点
 * @return {boolean} - 如果二叉树对称返回true，否则返回false
 */
var isSymmetric = function (root) {
  // 空树被认为是对称的
  if (root === null) return true;

  /**
   * 递归比较两个子树是否镜像对称
   * @param {TreeNode} left - 左子树节点
   * @param {TreeNode} right - 右子树节点
   * @return {boolean} - 如果两个子树镜像对称返回true，否则返回false
   */
  let compare = (left, right) => {
    // 两个节点都为空，对称
    if (left === null && right === null) return true;

    // 一个节点为空，另一个不为空，不对称
    if (left !== null && right === null) return false;
    if (left === null && right !== null) return false;

    // 两个节点值不相等，不对称
    if (left.val !== right.val) return false;

    // 递归比较：
    // 1. 左子树的左节点与右子树的右节点（外侧比较）
    // 2. 左子树的右节点与右子树的左节点（内侧比较）
    return compare(left.left, right.right) && compare(left.right, right.left);
  };

  // 从根节点的左右子树开始比较
  return compare(root.left, root.right);
};

104.二叉树的最大深度 ​

js
/**
 * 使用后序遍历（左右根）的方式，先处理左右子树，再处理当前节点
 * @param {TreeNode}
 * @return {number}
 */
var maxDepth = function (root) {
  // 边界情况：如果根节点为空，深度为0
  if (root === null) return 0;
  let dfs = (tree) => {
    // 递归终止条件：当前节点为空，深度为0
    if (tree == null) return 0;
    // 先递归处理左子树，获取左子树的最大深度
    let l = dfs(tree.left);
    // 再递归处理右子树，获取右子树的最大深度
    let r = dfs(tree.right);

    // 当前节点的深度 = 左右子树深度的最大值 + 1（当前节点本身）
    return Math.max(l, r) + 1;
  };

  // 从根节点开始递归计算最大深度
  return dfs(root);
};

111.二叉树的最小深度 ​

js
/**
 * @param {TreeNode}
 * @return {number}
 */
var minDepth = function (root) {
  // 边界情况：如果根节点为空，深度为0
  if (root === null) return 0;
  let dfs = (tree) => {
    // 递归终止条件：当前节点为空，深度为0
    if (tree === null) return 0;

    // 递归计算左子树的最小深度
    let l = dfs(tree.left);
    // 递归计算右子树的最小深度
    let r = dfs(tree.right);

    // 关键逻辑：如果左子树或右子树为空（深度为0）
    // 则不能取最小值（因为空子树不是叶子节点）
    // 这种情况下，最小深度是非空子树的深度+1
    if (l === 0 || r === 0) {
      return Math.max(l, r) + 1;
    }

    // 如果左右子树都不为空，取较小深度+1
    return Math.min(l, r) + 1;
  };

  // 从根节点开始递归计算最小深度
  return dfs(root);
};

222.完全二叉树的节点个数 ​

js
/**
 * 计算二叉树节点数量（采用后序遍历递归实现）
 * 关键思路：二叉树节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）
 * @param {TreeNode}
 * @return {number}
 */
var countNodes = function (root) {
  // 处理空树情况
  if (root === null) return 0;

  /**
   * 递归函数执行后序遍历
   * @param {TreeNode} tree - 当前子树根节点
   * @return {number} 当前子树的节点总数
   */
  let dfs = (tree) => {
    // 递归终止条件：当前节点为空
    if (tree === null) return 0;

    // 递归计算左子树节点数
    let leftCount = dfs(tree.left);
    // 递归计算右子树节点数
    let rightCount = dfs(tree.right);

    // 返回左子树节点数 + 右子树节点数 + 当前节点
    return leftCount + rightCount + 1;
  };

  // 从根节点开始遍历
  return dfs(root);
};

110.平衡二叉数 ​

解释 ​

  • 高度平衡二叉树定义： 每个节点的左右两个子树的高度差的绝对值不超过 1
  • 高度定义： 到叶子节点的距离
  • 深度定义： 到跟节点的距离
js
/**
 * 高度平衡二叉树定义：每个节点的左右两个子树的高度差的绝对值不超过1
 * 采用后序遍历递归实现，在计算高度的同时判断平衡性
 * @param {TreeNode}
 * @return {boolean}
 */
var isBalanced = function (root) {
  // 空树被认为是平衡的
  if (root === null) return true;

  /**
   * 递归函数执行后序遍历，计算子树高度并判断平衡性
   * @param {TreeNode} tree - 当前子树根节点
   * @return {number} 返回子树高度，如果子树不平衡则返回-1
   */
  let dfs = (tree) => {
    // 递归终止条件：空节点高度为0
    if (tree === null) return 0;

    // 提前检查左子树是否平衡，不平衡则直接返回-1
    if (dfs(tree.left) === -1) return -1;
    // 提前检查右子树是否平衡，不平衡则直接返回-1
    if (dfs(tree.right) === -1) return -1;

    // 计算左子树高度
    let leftHeight = dfs(tree.left);
    // 计算右子树高度
    let rightHeight = dfs(tree.right);

    // 判断当前节点是否平衡：左右子树高度差不超过1
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;

    // 返回当前子树高度：左右子树中较大高度+1
    return Math.max(leftHeight, rightHeight) + 1;
  };

  return dfs(root) !== -1;
};

257.二叉数的所有路径 ​

js
/**
 * 采用先序遍历递归实现
 * @param {TreeNode}
 * @return {string[]}
 */
var binaryTreePaths = function (root) {
  let result = [];
  let getPath = (node, currentPath) => {
    // 递归终止条件：当前节点为空
    if (node === null) return;

    // 叶子节点处理：将完整路径添加到结果集
    if (node.left === null && node.right === null) {
      result.push(currentPath + node.val);
      return;
    }

    // 非叶子节点处理：将当前节点值添加到路径中，并继续遍历左右子树
    currentPath += node.val + "->";
    getPath(node.left, currentPath);
    getPath(node.right, currentPath);
  };
  getPath(root, "");
  return result;
};

404.二叉数左叶子之和 ​

js
/**
 * 计算二叉树所有左叶子节点的和（采用后序遍历递归实现）
 * @param {TreeNode}
 * @return {number}
 */
var sumOfLeftLeaves = function (root) {
  // 处理空树和单节点树的情况（单节点树的根节点不算左叶子）
  if (root === null) return 0;
  if (root.left === null && root.right === null) return 0;

  let getSum = (node) => {
    // 递归终止条件：当前节点为空
    if (node === null) return 0;

    // 递归计算左子树中的左叶子节点和
    let leftSum = getSum(node.left);
    // 递归计算右子树中的左叶子节点和
    let rightSum = getSum(node.right);

    let currentSum = 0;
    // 检查当前节点的左子节点是否为叶子节点
    if (
      node.left !== null &&
      node.left.left === null &&
      node.left.right === null
    ) {
      currentSum += node.left.val;
    }

    return currentSum + leftSum + rightSum;
  };

  return getSum(root);
};

513.找树左下角的值 ​

js
/**
 * 寻找二叉树最底层最左边的节点值（采用层序遍历/BFS实现）
 * @param {TreeNode}
 * @return {number}
 */
var findBottomLeftValue = function (root) {
  // 处理空树的情况
  if (root === null) return 0;

  // 初始化队列，从根节点开始遍历
  let queue = [root];
  let result = 0;

  // 层序遍历
  while (queue.length > 0) {
    // 记录当前层的节点数量
    let size = queue.length;

    // 记录当前层的第一个节点值（最左边的节点）
    result = queue[0].val;

    // 遍历当前层的所有节点
    while (size--) {
      let node = queue.shift();

      // 将左子节点加入队列（先左后右，保证下一层顺序正确）
      if (node.left !== null) {
        queue.push(node.left);
      }

      // 将右子节点加入队列
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }

  return result;
};

112.二叉数路径总和 ​

js
/**
 * 先序遍历：叶子节点求和对比
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (root === null) return false;
  let result = false;
  let dfs = (node, sum) => {
    if (result) return true;
    if (node === null) return 0;
    // 叶子节点
    if (node.left === null && node.right === null) {
      if (sum + node.val === targetSum) {
        result = true;
        return;
      }
    }
    // 非叶子节点累加
    sum += node.val;
    dfs(node.left, sum);
    dfs(node.right, sum);
  };
  dfs(root, 0);
  return result;
};

106.从中序与后序遍历序列构造二叉树 ​

解题思路： ​

  1. 后序遍历的最后一个元素是根节点。
  2. 在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
  3. 递归构建左子树和右子树。
js
/**
 * @param {number[]} inorder 中序遍历序列
 * @param {number[]} postorder 后序遍历序列
 * @return {TreeNode} 重建的二叉树根节点
 */
var buildTree = function (inorder, postorder) {
  // 如果后序遍历序列为空，说明当前子树无节点，返回null
  if (postorder.length === 0) return null;

  // 后序遍历的最后一个元素即为当前子树的根节点值
  let nodeVal = postorder.pop();

  // 在中序遍历序列中找到根节点的位置
  let rootIndex = inorder.indexOf(nodeVal);

  // 创建当前根节点
  let root = new TreeNode(nodeVal);

  // 递归构建左子树：
  // - 左子树的中序遍历序列为根节点左侧部分：inorder[0:rootIndex]
  // - 左子树的后序遍历序列为后序序列的前rootIndex个元素：postorder[0:rootIndex]
  root.left = buildTree(
    inorder.slice(0, rootIndex),
    postorder.slice(0, rootIndex)
  );

  // 递归构建右子树：
  // - 右子树的中序遍历序列为根节点右侧部分：inorder[rootIndex+1:]
  // - 右子树的后序遍历序列为后序序列的rootIndex开始到末尾：postorder[rootIndex:]
  root.right = buildTree(
    inorder.slice(rootIndex + 1),
    postorder.slice(rootIndex)
  );

  return root;
};

105.从前序与中序遍历序列构造二叉树 ​

解题思路： ​

  1. 前序遍历的第一个元素是根节点。
  2. 在中序遍历中找到根节点的位置，从而确定左子树和右子树的范围。
  3. 递归构建左子树和右子树。
js
/**
 * @param {number[]} preorder 前序遍历序列
 * @param {number[]} inorder 中序遍历序列
 * @return {TreeNode} 重建的二叉树根节点
 */
var buildTree = function (preorder, inorder) {
  // 如果前序遍历序列为空，说明当前子树无节点，返回null
  if (preorder.length === 0) return null;

  // 前序遍历的第一个元素即为当前子树的根节点值
  let nodeVal = preorder[0];

  // 创建当前根节点
  let root = new TreeNode(nodeVal);

  // 在中序遍历序列中找到根节点的位置
  let rootIndex = inorder.indexOf(nodeVal);

  // 递归构建左子树：
  // - 左子树的前序遍历序列为前序序列中从索引1开始，长度为rootIndex的部分
  // - 左子树的中序遍历序列为中序序列中从开始到根节点位置的部分
  root.left = buildTree(
    preorder.slice(1, rootIndex + 1),
    inorder.slice(0, rootIndex)
  );

  // 递归构建右子树：
  // - 右子树的前序遍历序列为前序序列中从rootIndex+1开始到末尾的部分
  // - 右子树的中序遍历序列为中序序列中从根节点位置+1到末尾的部分
  root.right = buildTree(
    preorder.slice(rootIndex + 1),
    inorder.slice(rootIndex + 1)
  );

  return root;
};

654.最大二叉树 ​

解题思路： ​

  1. 找到数组中的最大值，作为当前子树的根节点。
  2. 在数组中找到最大值的索引，从而确定左子树和右子树的范围。
  3. 递归构建左子树和右子树。
js
/**
 * @param {number[]} nums 输入数组
 * @return {TreeNode} 构建的最大二叉树的根节点
 */
var constructMaximumBinaryTree = function (nums) {
  // 如果数组为空，返回null（递归的基本情况）
  if (nums.length === 0) return null;

  // 初始化最大值和其索引
  let maxVal = 0;
  let maxIndex = 0;

  // 遍历数组找到最大值及其索引
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > maxVal) {
      maxVal = nums[i];
      maxIndex = i;
    }
  }

  // 创建当前根节点，值为最大值
  const rootNode = new TreeNode(maxVal);

  // 递归构建左子树：使用最大值左边的子数组
  rootNode.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));

  // 递归构建右子树：使用最大值右边的子数组
  rootNode.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));

  // 返回构建好的树
  return rootNode;
};

617.合并二叉树 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1 第一个二叉树的根节点
 * @param {TreeNode} root2 第二个二叉树的根节点
 * @return {TreeNode} 合并后的二叉树根节点
 */
var mergeTrees = function (root1, root2) {
  // 使用深度优先搜索(DFS)递归合并两棵树
  let dfs = (root1, root2) => {
    // 如果第一棵树当前节点为空，返回第二棵树的当前节点（包括其所有子树）
    if (!root1) return root2;

    // 如果第二棵树当前节点为空，返回第一棵树的当前节点（包括其所有子树）
    if (!root2) return root1;

    // 两个节点都存在，将它们的值相加
    root1.val += root2.val;

    // 递归合并左子树
    root1.left = dfs(root1.left, root2.left);

    // 递归合并右子树
    root1.right = dfs(root1.right, root2.right);

    // 返回合并后的节点
    return root1;
  };

  // 从根节点开始合并
  return dfs(root1, root2);
};

700.二叉搜索树中的搜索 ​

js
/**
 * @param {TreeNode} root 二叉搜索树的根节点
 * @param {number} val 要搜索的值
 * @return {TreeNode} 包含目标值的节点，如果不存在则返回null
 */
var searchBST = function (root, val) {
  // 如果根节点为空，直接返回null
  if (root === null) return null;

  // 定义递归搜索函数
  let search = (node) => {
    // 如果节点为空或找到目标值，返回当前节点
    if (node === null || node.val === val) return node;

    // 如果目标值小于当前节点值，在左子树中搜索
    if (val < node.val) {
      return search(node.left);
    }

    // 如果目标值大于当前节点值，在右子树中搜索
    if (val > node.val) {
      return search(node.right);
    }
  };

  // 从根节点开始搜索
  return search(root);
};

98.验证二叉搜索树 ​

解题思路： ​

  1. 中序遍历：二叉搜索树的中序遍历结果是一个递增序列。我们可以通过中序遍历二叉树，并检查遍历结果是否为递增序列来判断是否为二叉搜索树。
  2. 递归：在递归过程中，我们需要记录当前节点的值，并检查当前节点的值是否大于前一个节点的值（即递增）。
js
/**
 * @param {TreeNode} root 二叉树的根节点
 * @return {boolean} 如果是有效的二叉搜索树则返回true，否则返回false
 */
var isValidBST = function (root) {
  // 空树被认为是有效的二叉搜索树
  if (root === null) return true;

  // 用于存储中序遍历结果的数组
  let result = [];

  // 中序遍历函数：左子树 -> 根节点 -> 右子树
  let dfs = (node) => {
    if (node === null) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  };

  // 执行中序遍历
  dfs(root);

  let slow = 0;
  let fast = 1;
  while (fast < result.length) {
    if (result[slow] >= result[fast]) {
      return false;
    }
    slow++;
    fast++;
  }

  return true;
};

530.二叉搜索树的最小绝对差 ​

js
/**
 * 计算二叉搜索树中任意两节点差的最小值
 * 利用二叉搜索树中序遍历为有序序列的特性
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
  // 存储中序遍历结果
  let result = [];

  // 递归中序遍历函数
  let dfs = (node) => {
    if (node === null) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  };

  // 执行中序遍历
  dfs(root);

  // 初始化最小差值为极大值
  let minVal = Infinity;

  // 使用双指针遍历有序数组，计算相邻元素差值
  let i = 0;
  let j = 1;
  while (j < result.length) {
    let diff = result[j] - result[i];
    if (diff < minVal) {
      minVal = diff;
    }
    i++;
    j++;
  }

  return minVal;
};

501.二叉搜索树中的众数 ​

js
/**
 * 中序遍历 - 查找二叉搜索树中的众数（出现频率最高的元素）
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
  // 处理空树的情况
  if (root === null) return [];

  // 初始化变量
  let maxCount = 1; // 当前最高出现次数
  let count = 0; // 当前数字的连续出现次数
  let result = []; // 存储众数结果
  let preNode = root; // 记录前一个访问的节点

  // 中序遍历的递归函数
  let dfs = (node) => {
    if (node === null) return;

    // 递归遍历左子树
    dfs(node.left);

    // 判断是否是第一个节点或当前节点值是否与前一个节点值相同
    if (node.val === preNode.val) {
      count++; // 相同则计数增加
    } else {
      count = 1; // 不同则重置计数为1
    }

    // 判断当前计数与最大计数的关系
    if (count === maxCount) {
      // 如果当前数字出现次数等于最大次数，加入结果集
      result.push(node.val);
    } else if (count > maxCount) {
      // 如果当前数字出现次数超过最大次数
      result = [node.val]; // 清空之前的结果并添加新的众数
      maxCount = count; // 更新最大次数
    }

    // 更新前一个节点为当前节点
    preNode = node;

    // 3. 递归遍历右子树
    dfs(node.right);
  };

  // 从根节点开始中序遍历
  dfs(root);
  return result;
};

160.相交链表 ​

力扣题目链接

题目描述 ​

  • 找到两个单链表相交的起始节点。如果两个链表没有交点，则返回 null。

思路 ​

  1. 双指针法：
    • 初始化两个指针 pA 和 pB，分别指向链表 A 和 B 的头节点。
    • 遍历链表，当指针到达链表末尾时，跳到另一个链表的头节点继续遍历。
    • 当两个指针相遇时，即为相交节点。
  2. 原理：
    • 假设链表 A 的长度为 m，链表 B 的长度为 n，相交部分长度为 c。

数学解释：操场比喻与路径平衡原理 ​

  • A 操场：总长 40 米（20 米独有跑道 + 20 米共享跑道）
  • B 操场：总长 50 米（30 米独有跑道 + 20 米共享跑道）

双指针运动轨迹 ​

  • A,B 跑 70 米处相遇

  1. 指针 A 路径：

    • 先跑完 A 操场独有 20 米
    • 再跑完 B 操场独有 30 米
    • 最后进入共享跑道
    • 总路程 = 20 + 30 + 20 = 70 米

  2. 指针 B 路径：

    • 先跑完 B 操场独有 30 米
    • 再跑完 A 操场独有 20 米
    • 最后进入共享跑道
    • 总路程 = 30 + 20 + 20 = 70 米

示例演示 ​

场景 1：相交链表

text
链表 A：`4 → 1 → 8 → 4 → 5`
链表 B：`5 → 6 → 1 → 8 → 4 → 5`（相交节点 `8`）
指针 A 路径：4→1→8→4→5→5→6→1→[8]
指针 B 路径：5→6→1→8→4→5→4→1→[8]
                             ↑ 相遇点

场景 2：不相交链表

text
链表 A：`2 → 6 → 4`
链表 B：`1 → 5`
指针 A 路径：2→6→4→1→5→null
指针 B 路径：1→5→2→6→4→null
                        ↑ 同时为 null

代码实现 ​

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

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = function (headA, headB) {
  // 边界条件
  if (headA === null || headB === null) return null;
  let pointA = headA;
  let pointB = headB;
  // 如果两个链表相交，则两个指针一定会在相交节点处相遇
  // 如果两个链表不相交，则两个指针最终会同时到达链表末尾（null）
  while (pointA !== pointB) {
    //  if (pointA === null) {
    //    pointA = headB;
    //  } else {
    //    pointA = pointA.next;
    //  }
    //  if (pointB === null) {
    //    pointB = headA;
    //  } else {
    //    pointB = pointB.next;
    //  }
    pointA = pointA ? pointA.next : headB;
    pointB = pointB ? pointB.next : headA;
  }
  return pointA;
};

328.奇偶链表 ​

力扣题目链接

题目描述 ​

  • 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

思路 ​

  1. 分离奇偶节点：
    • 使用两个指针 odd 和 even 分别遍历奇数节点和偶数节点。
    • 奇数节点链：从头节点（节点 1）开始，连接所有奇数位置的节点。
    • 偶数节点链：从第二个节点（节点 2）开始，连接所有偶数位置的节点。
  2. 合并链表：
    • 遍历结束后，将奇数链表的尾部连接到偶数链表的头部。

算法步骤 ​

  1. 边界处理：若链表为空、只有一个节点或只有两个节点，直接返回 head。
  2. 初始化指针：
    • odd 指向头节点（第一个奇数节点）。
    • even 指向第二个节点（第一个偶数节点），并保存 evenHead 作为偶数链表的头。
  3. 遍历链表：
    • 将 odd.next 指向 even.next（下一个奇数节点）。
    • 移动 odd 到下一个奇数节点。
    • 将 even.next 指向 odd.next（下一个偶数节点）。
    • 移动 even 到下一个偶数节点。
  4. 合并链表：将奇数链表的尾部（odd）连接到偶数链表的头部（evenHead）。

示例演示 ​

示例：1 → 2 → 3 → 4 → 5

  1. 分离奇偶链：
    • 奇数链：1 → 3 → 5
    • 偶数链：2 → 4
  2. 合并：将奇数链尾部（5）连接偶数链头部（2）
  3. 结果：1 → 3 → 5 → 2 → 4
  • 双指针 odd（奇数节点）和 even（偶数节点）同步移动
  • 每次操作：
    1. odd.next = even.next（链接下一个奇数节点）
    2. even.next = odd.next（链接下一个偶数节点）
  • 最后用 evenHead 连接两个链表

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
  // 边界条件
  if (head === null || head.next === null || head.next.next === null)
    return head;
  let odd = head; // 奇数节点链表头
  let even = head.next; // 偶数节点链表头
  let evenHead = even; // 保存偶数节点链表头
  // 如果偶数，后面还有节点(奇数)
  while (even && even.next) {
    // 奇数&偶数节点连接
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  // 奇数节点链表尾部连接偶数节点链表头部
  odd.next = evenHead;
  return head;
};

92.反转链表|| ​

力扣题目链接

题目描述 ​

  • 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路 ​

  • 1、构建⼀个虚拟节点，让它指向原链表的头节点。
  • 2、设置两个指针，pre 指针指向以虚拟头节点为链表的头部位置，cur 指针指向原链表的头部位置。
  • 3、让着两个指针向前移动，直到 pre 指向了第⼀个要反转的节点的前⾯那个节点，⽽ cur 指向了第⼀个要反转的节点。
  • 4、开始指向翻转操作
    • 1）、设置临时变量 node，node 是 cur 的 next 位置，保存当前需要翻转节点的后⾯的节点，我们需要交换 node 和 cur
    • 2）、让 cur 的 next 位置变成 node 的下⼀个节点
    • 3）、让 node 的 next 位置变成 cur
    • 4）、让 pre 的 next 位置变成 node

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
const reverseBetween = function (head, left, right) {
  // 边界条件
  if (head === null) return null;
  // 创建一个虚拟头节点
  let dummy = {
    next: head,
  };
  // 双两个指针
  let pre = dummy;
  let cur = head;
  // 定位到left位置
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next; // 因为需要反转，所以需要来的需要反转的前一个节点
    cur = cur.next;
  }
  // 反转链表
  for (let index = 0; index < right - left; index++) {
    let node = cur.next; // 保存当前节点的下一个节点
    cur.next = node.next; // 当前节点指向下一个节点的下一个节点
    node.next = pre.next; // 下一个节点指向当前节点的下一个节点
    pre.next = node; // 当前节点指向下一个节点
  }
  return dummy.next;
};

234.回文链表 ​

力扣题目链接

题目描述 ​

  • 请判断一个链表是否为回文链表。(正序和倒序读值都一样)

思路 ​

使用快慢指针法解决回文链表问题：

  1. 快慢指针定位中点：快指针每次走两步，慢指针每次走一步
  2. 反转后半部分：从慢指针位置开始反转链表后半部分
  3. 比较前后两半：比较前半部分和反转后的后半部分是否相同
  4. 恢复链表结构（可选）：如果需要保持原链表结构，可以再次反转恢复

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = function (head) {
  // 空链表和单节点链表是回文链表
  if (head === null) {
    return true;
  }
  // 2个节点链表，判断是否相等
  if (head.next !== null && head.next.next === null) {
    return head.val === head.next.val;
  }
  let slow = head; // 慢
  let fast = head; // 快
  // 循环结束后，slow指向中间节点，fast指向末尾节点
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let leftHead = head; // 前半部分链表头
  let rightHead = reverseList(slow.next); // 后半部分链表头(反转之后的)

  // 循环对比
  while (rightHead) {
    if (leftHead.val !== rightHead.val) {
      return false;
    }
    leftHead = leftHead.next;
    rightHead = rightHead.next;
  }
  return true;
};

const reverseList = (head) => {
  let pre = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = pre;
    per = cur;
    cur = next;
  }
  return pre;
};

82.删除排序链表中的重复元素|| ​

力扣题目链接

题目描述 ​

  • 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

思路 ​

是使用哨兵节点（dummy node） 处理头节点可能被删除的情况，通过双指针遍历识别并删除重复元素：

  1. 哨兵节点：创建一个指向头节点的哨兵节点，解决头节点被删除时的边界问题
  2. 双指针遍历：
    • 使用 cur 指针从哨兵节点开始遍历
    • 当检测到重复时（cur.next.val === cur.next.next.val）：
      • 记录重复值 x
      • 循环删除所有值为 x 的节点
    • 当无重复时，正常移动指针
  3. 终止条件：当后续不足两个节点时停止检测

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function (head) {
  // 边界条件
  if (head === null) return null;
  // 创建一个虚拟头节点
  let dummy = {
    next: head,
  };
  // 当前节点,从虚拟头节点开始
  let cur = dummy;

  while (cur.next && cur.next.next) {
    // 如果当前节点的下一个节点和下下个节点值相等,则说明有重复节点
    // 删除重复节点
    if (cur.next.val === cur.next.next.val) {
      let x = cur.next.val;
      while (cur.next && cur.next.val === x) {
        cur.next = cur.next.next;
      }
    } else {
      // 否则，当前节点后移
      cur = cur.next;
    }
  }
  return dummy.next;
};

83.删除排序链表中的重复元素 ​

力扣题目链接

题目描述 ​

  • 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

思路 ​

题目要求删除排序链表中的重复元素，保留每个元素的第一次出现。由于链表已排序，重复元素必然相邻，因此只需遍历一次链表：

  1. 单指针遍历：使用指针 cur 从链表头开始遍历
  2. 重复检测：比较当前节点与下一节点的值
    • 若相等：跳过下一节点（cur.next = cur.next.next）
    • 若不相等：移动指针到下一节点
  3. 终止条件：当当前节点或下一节点为空时停止

示例演示 ​

示例演示 ​

以输入链表 [1, 1, 2, 3, 3] 为例：

  1. 第一轮：1 与 1 重复 → 跳过第二个 1，链表变为 [1, 2, 3, 3]
  2. 第二轮：1 与 2 不重复 → 移动指针到 2
  3. 第三轮：2 与 3 不重复 → 移动指针到 3
  4. 第四轮：3 与 3 重复 → 跳过第二个 3，链表变为 [1, 2, 3]
  5. 返回结果：[1, 2, 3]

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  // 边界条件
  if (head === null) return null;
  // 当从节点开始
  let cur = head;
  // 如果有下一个节点，循环
  while (cur && cur.next) {
    // 如果当前节点和下一个节点值相等，跳过下一个节点
    if (cur.val == cur.next.val) {
      cur.next = cur.next.next;
    } else {
      // 否则，移动指针到下一个节点
      cur = cur.next;
    }
  }
  return head;
};

86.分割链表 ​

力扣题目链接

题目描述 ​

  • 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

思路 ​

  1. 创建两个虚拟（Dummy Nodes）：

    • minHead：用于链接所有小于 x 的节点。
    • maxHead：用于链接所有大于等于 x 的节点。

  2. 遍历原链表：

    • 若当前节点值 < x，将其链接到 minHead 的链表末尾。
    • 若当前节点值 >= x，将其链接到 maxHead 的链表末尾。

  3. 合并链表：

    • 将 minHead 链表的末尾指向 maxHead 链表的头节点（跳过哑节点）。
    • 将 maxHead 链表的末尾节点的 next 置为 null（避免循环）。

  4. 返回结果：

    • 返回 minHead.next（跳过哑节点）。

示例演示 ​

以输入 head = [1,4,3,2,5,2], x = 3 为例：

  1. 初始化两个虚拟节点：minHead 和 maxHead。
  2. 遍历链表：
    • 1 < 3 → 加入 min 链表：minHead → 1
    • 4 >= 3 → 加入 max 链表：maxHead → 4
    • 3 >= 3 → 加入 max 链表：maxHead → 4 → 3
    • 2 < 3 → 加入 min 链表：minHead → 1 → 2
    • 5 >= 3 → 加入 max 链表：maxHead → 4 → 3 → 5
    • 2 < 3 → 加入 min 链表：minHead → 1 → 2 → 2
  3. 合并链表：
    • min 链表末尾（节点 2）指向 max 链表头（节点 4）：1 → 2 → 2 → 4 → 3 → 5
    • 将 max 链表末尾（节点 5）的 next 置为 null。
  4. 返回 minHead.next（即节点 1）。

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
const partition = function (head, x) {
  if (head === null) return null;
  let minHead = {
    next: null,
  };
  let min = minHead;
  let maxHead = {
    next: null,
  };
  let max = maxHead;
  let cur = head;
  while (cur) {
    if (cur.val < x) {
      min.next = cur;
      min = min.next;
    } else {
      max.next = cur;
      max = max.next;
    }
    cur = cur.next;
  }
  // 后面可能有小于x的节点，所以需要断开
  max.next = null;
  min.next = maxHead.next;
  return minHead.next;
};

21.合并 2 个有序链表 ​

力扣题目链接

题目描述 ​

  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路 ​

迭代法：

  1. 边界处理：
    • 若两链表均为空 → 返回 null
    • 若一链表为空 → 返回另一链表
  2. 虚拟头节点：
    • 创建 dummy 节点简化边界处理
    • 用 head 指针追踪合并链表的尾部
  3. 双指针比较：
    • 同时遍历两链表
    • 比较节点值，将较小值接入合并链表
    • 移动较小值所在链表的指针
  4. 处理剩余节点：
    • 当一链表遍历完，将另一链表剩余部分直接接入
  5. 返回结果：
    • 返回 dummy.next（真实头节点）

示例演示 ​

输入：
list1 = 1 → 3 → 5
list2 = 2 → 4 → 6

合并过程：

  1. 比较 1 vs 2 → 接入 1：
    合并链表：dummy → 1
    list1 → 3, list2 → 2
  2. 比较 3 vs 2 → 接入 2：
    合并链表：dummy → 1 → 2
    list1 → 3, list2 → 4
  3. 比较 3 vs 4 → 接入 3：
    合并链表：dummy → 1 → 2 → 3
    list1 → 5, list2 → 4
  4. 比较 5 vs 4 → 接入 4：
    合并链表：dummy → 1 → 2 → 3 → 4
    list1 → 5, list2 → 6
  5. 比较 5 vs 6 → 接入 5：
    合并链表：dummy → 1 → 2 → 3 → 4 → 5
    list1 → null
  6. 接入 list2 剩余节点 6：
    合并链表：dummy → 1 → 2 → 3 → 4 → 5 → 6

输出：1 → 2 → 3 → 4 → 5 → 6

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // 边界处理
  if (list1 === null && list2 === null) return null;
  // 若一链表为空 → 返回另一链表
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  // 虚拟头节点
  let dummy = {
    next: null,
  };
  let head = dummy;
  /// 双指针比较
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      head.next = list1;
      list1 = list1.next;
    } else {
      head.next = list2;
      list2 = list2.next;
    }
    // 移动合并链表尾部指针
    head = head.next;
  }
  // 直接连接剩余链表
  head.next = list1 || list2;
  return dummy.next;
};

138.随机链表的复制 ​

力扣题目链接

题目描述 ​

  • 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或 null。

思路 ​

复制带随机指针的链表需要解决的关键问题是：当复制节点时，随机指针指向的节点可能尚未创建。使用哈希表（Map）存储原节点到新节点的映射，通过两次遍历解决：

  1. 第一次遍历：创建所有新节点，建立原节点到新节点的映射（包括 null 映射）
  2. 第二次遍历：根据映射关系，设置新节点的 next 和 random 指针

示例演示 ​

代码实现 ​

javascript
/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function (head) {
  if (head === null) return null;

  // 创建哈希表并处理null映射
  const map = new Map();
  map.set(null, null); // 关键：确保null映射到null

  // 第一次遍历：创建所有新节点
  let cur = head;
  while (cur) {
    map.set(cur, new _Node(cur.val, null, null));
    cur = cur.next;
  }

  // 第二次遍历：获取所以的新节点映射
  cur = head;
  while (cur) {
    const newNode = map.get(cur);
    newNode.next = map.get(cur.next);
    newNode.random = map.get(cur.random);
    cur = cur.next;
  }

  return map.get(head);
};

61.旋转链表 ​

力扣题目链接

题目描述 ​

  • 给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const rotateRight = function (head, k) {
  if (head === null || k === 0) return head;
  let len = 1;
  let temp = head;
  while (temp.next) {
    temp = temp.next;
    len++;
  }
  k = k % len; // 处理k大于链表长度的情况
  let slow = head;
  let fast = head;
  for (let i = 0; i < k; i++) {
    slow = slow.next;
  }
  while (slow.next) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = head;
  let newHead = fast.next;
  fast.next = null;
  return newHead;
};

143.重排链表 ​

力扣题目链接

题目描述 ​

  • 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
  • 1->2->3->4->5 重排为 1->5->2->4->3

思路 ​

重排链表的关键是将链表分成两半，反转后半部分，然后交替合并。具体步骤如下：

  1. 快慢指针找中点：

    • 使用快慢指针技巧找到链表中点（慢指针每次走 1 步，快指针每次走 2 步）
    • 当快指针到达末尾时，慢指针正好指向中点（奇数链表指向中间节点，偶数链表指向前半部分末尾）

  2. 断开并反转后半部分：

    • 将链表从中点后断开，形成两个独立链表
    • 反转后半部分链表（使最后节点变为头节点）

  3. 交替合并链表：

    • 将前半部分和反转后的后半部分交替合并
    • 每次取前半部分一个节点和后半部分一个节点连接

示例演示 ​

示例 1：1->2->3->4

  1. 找中点：slow 停在 2（fast 停在 3）
  2. 断开：前半部分 1->2，后半部分 3->4
  3. 反转后半部分：4->3
  4. 交替合并：
    • 1->4->2->3

示例 2：1->2->3->4->5

  1. 找中点：slow 停在 3（fast 停在 5）
  2. 断开：前半部分 1->2->3，后半部分 4->5
  3. 反转后半部分：5->4
  4. 交替合并：
    • 1->5->2->4->3

代码实现 ​

javascript
const reorderList = function (head) {
  // 空链表或单节点直接返回
  if (!head || !head.next) return;

  // 1. 快慢指针找中点（slow停在前半部末尾）
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. 断开链表并反转后半部分
  let secondHalf = slow.next; // 后半部分头节点
  slow.next = null; // 关键：断开前后链表

  // 反转后半部分
  let prev = null;
  let curr = secondHalf;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  secondHalf = prev; // prev成为反转后的头节点

  // 3. 交替合并两个链表
  let first = head;
  let second = secondHalf;
  while (first && second) {
    // 保存下一节点
    const firstNext = first.next;
    const secondNext = second.next;

    // 交替连接节点
    first.next = second;
    second.next = firstNext;

    // 移动指针
    first = firstNext;
    second = secondNext;
  }
};

876.链表的中间节点 ​

力扣题目链接

题目描述 ​

  • 给定一个链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

思路 ​

寻找链表中间节点的标准解法是使用快慢指针技巧：

  1. 快指针每次移动两步
  2. 慢指针每次移动一步
  3. 当快指针到达链表末尾时，慢指针正好位于中间位置

关键点：

  • 链表节点数为奇数时，慢指针停在唯一中间节点
  • 链表节点数为偶数时，慢指针停在第二个中间节点（题目要求）

示例演示 ​

示例 1：奇数节点 (1→2→3→4→5)

步骤   slow    fast
0:     1       1
1:     2       3
2:     3       5 → 停止（fast.next=null）
返回节点3

示例 2：偶数节点 (1→2→3→4→5→6)

步骤   slow    fast
0:     1       1
1:     2       3
2:     3       5
3:     4       null → 停止
返回节点4

代码实现 ​

javascript
const middleNode = function (head) {
  let slow = head;
  let fast = head;

  // 快指针每次移动两步，慢指针每次移动一步
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
};

3. 无重复字符的最长子串 ​

力扣题目链接

题目描述 ​

  • 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思路 ​

示例演示 ​

代码实现 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let left = 0;
  let result = 0;
  let charSet = new Set();

  for (let right = 0; right < s.length; right++) {
    let str = s[right];
    while (charSet.has(str)) {
      charSet.delete(s[left++]);
    }
    result = Math.max(result, right - left + 1);
    charSet.add(str);
  }
  return result;
};