合并两个有序链表、手撕快排、螺旋矩阵

合并两个有序链表

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

思路：用一个幽灵节点 dummy 记忆头节点

记住最后不需要像数组那样单独循环 list1 和 list2，直接 if 它们还有没有节点，然后直接接上就行

注意是升序，比较大小的时候不要搞错了

ts
    const dummy = new ListNode();
    let p = dummy;

    while(list1 && list2){
        if(list1.val < list2.val){
            p.next = list1;
            list1 = list1.next;
        } else {
            p.next = list2;
            list2 = list2.next;
        };
        p = p.next;
    };

    if(list1){
        p.next = list1;
    };

    if(list2){
        p.next = list2;
    };

    return dummy.next;
};

手撕快速排序

思路：

选择一个基准值 pivot，一般是数组第一个元素
分区：小的放左边，大的放右边
递归对左右两部分排序
合并结果

和归并的区别：归并是先不断递归拆分，只剩下单个元素；合并时保持顺序

注意：

原地排序 partition：先用随机数取 pivotIdx，让 nums[hi] 和 nums[pivotIdx] 交换位置，再标记 pivot 为 nums[pivotIdx]
partition 循环终止条件是 i <= gt 而非 i <= hi，因为 gt 之后的已经被排好序了
partition 循环里，注意 nums[i] 的比较对象是 pivot；nums[i] < pivot 时 i 要自增，但 nums[i] <> pivot 只要 gt--（注意不是 gt++）
solution 的无效条件是 lo >= hi 而不是 nums.length < 2；partition 不需要判定 nums.length < 2

ts
function sortArray(nums: number[]): number[] {
  solution(nums, 0, nums.length - 1);

  return nums;
}

const solution = (nums, lo, hi) => {
  if (lo >= hi) {
    return;
  }

  const [lt, gt] = partition(nums, lo, hi);
  solution(nums, lo, lt - 1);
  solution(nums, gt + 1, hi);
};

const partition = (nums: number[], lo: number, hi: number) => {
  const pivotIdx = Math.floor(Math.random() * (hi - lo + 1)) + lo;
  [nums[pivotIdx], nums[hi]] = [nums[hi], nums[pivotIdx]];
  const pivot = nums[hi];

  let i = lo,
    lt = lo,
    gt = hi;
  while (i <= hi) {
    if (nums[i] < pivot) {
      [nums[i], nums[lt]] = [nums[lt], nums[i]];
      lt++;
      i++;
    } else if (nums[i] > pivot) {
      [nums[i], nums[gt]] = [nums[gt], nums[i]];
      gt--;
    } else {
      i++;
    }
  }

  return [lt, gt];
};

螺旋矩阵

给定一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出：[1,2,3,6,9,8,7,4,5]

思路：

判定是否需要转向：用 set 存储已经访问过的 {i},{j}，若超出边界或 visited.has('{i},{j}')，则需要 dir = (dir + 1) % 4
for 循环里每次进入新循环时，该坐标必定有效，因为后面的操作保证了 i, j 都是有效的。所以从一开始就可以 visited.add('{i},{j}')（也确保第一个可以被访问到），然后再对 new_i 和 new_j 的有效性进行判定（如果无效就转向）
for 的终止条件是 i < m * n，保证刚好遍历完所有矩阵元素
注意 set 添加的方法是 add

ts
function spiralOrder(matrix: number[][]): number[] {
  if (!matrix.length || !matrix[0].length) {
    return [];
  }

  const m = matrix.length,
    n = matrix[0].length;
  const visited = new Set<string>();

  const direction = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];

  const isValid = (i, j) =>
    i < m && i >= 0 && j >= 0 && j < n && !visited.has(`${i},${j}`);

  let dir = 0,
    res = [];

  for (let i = 0, row = 0, col = 0; i < m * n; i++) {
    res.push(matrix[row][col]);
    visited.add(`${row},${col}`);

    let next_i = row + direction[dir][0];
    let next_j = col + direction[dir][1];

    if (!isValid(next_i, next_j)) {
      dir = (dir + 1) % 4;
      next_i = row + direction[dir][0];
      next_j = col + direction[dir][1];
    }

    row = next_i;
    col = next_j;
  }

  return res;
}