链表复制与回文

如何复制带随机指针的链表？

• 难点: random 可能指向尚未创建的结点, 不能一次遍历复制完;
• 第一趟: 只建新结点, 用 Map 记录 旧结点 → 新结点 (对象作键只能用 Map);
• 第二趟: map.get(cur).next = map.get(cur.next) ?? null, random 同理;
• 返回: map.get(head);
• 时间 $O(n)$, 空间 $O(n)$;

const copyRandomList = (head) => {
  const hash = new Map();
  for (let cur = head; cur; cur = cur.next) {
    hash.set(cur, new ListNode(cur.val));
  }
  for (let cur = head; cur; cur = cur.next) {
    hash.get(cur).next = hash.get(cur.next) ?? null;
    hash.get(cur).random = hash.get(cur.random) ?? null;
  }
  return hash.get(head) ?? null;
};

如何判断链表是否回文？

• 数组版 (234): 顺序收集结点值, 再用左右双指针比较;
• 链表版: 找中点 → 反转后半 → 两半同步比较, 空间 $O(1)$;
• 代价对比: 数组版写起来最短, 空间 $O(n)$;

const isPalindrome = (head) => {
  const arr = [];
  for (let cur = head; cur; cur = cur.next) arr.push(cur.val);

  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    if (arr[left] !== arr[right]) return false;
    left++;
    right--;
  }
  return true;
};