day009 有序链表转换二叉搜索树

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/
[制卡]

快慢指针

const sortedListToBST = (head) => {
  if (head == null) return null;
  let slow = head;
  let fast = head;
  let preSlow; // 保存slow的前一个节点
  while (fast && fast.next) {
    preSlow = slow;        // 保存当前slow
    slow = slow.next;      // slow走一步
    fast = fast.next.next; // fast走两步
  }
  const root = new TreeNode(slow.val);     // 根据slow指向的节点值，构建节点
  if (preSlow != null) {   // 如果preSlow有值，即slow左边有节点，需要构建左子树
    preSlow.next = null;   // 切断preSlow和中点slow
    root.left = sortedListToBST(head);     // 递归构建左子树
  }
  root.right = sortedListToBST(slow.next); // 递归构建右子树
  return root;
};

function sortedListToBST(head: ListNode | null): TreeNode | null {
  return build(head, null);
}

function build(left: ListNode | null, right: ListNode | null): TreeNode | null {
  if (left == right) {
    return null
  }
  let mid: ListNode = getMid(left, right) as ListNode
  let root = new TreeNode(mid.val)
  root.left = build(left,mid)
  root.right = build(mid.next,right)
  return root
}

function getMid(left: ListNode | null, right: ListNode | null): ListNode | null {
  // 快慢指针
  let slow = left;
  let fast = left;
  while (fast != null && fast.next != right) {
    slow = slow != null ? slow.next : null
    fast = fast.next != null ? fast.next.next : null
  }
  return slow
}