LeetCode.109 - 有序链表转换二叉搜索树

• LeetCode - 109. 有序链表转换二叉搜索树

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

思路

1. 与 《108 - 将有序数组转换为二叉搜索树》 类似
2. 可以使用双指针求得中间节点
3. 需要保留中间节点的前驱节点以便将其 next 置空
4. 需要考虑只有一个节点的情况处理

var sortedListToBST = function (head) {
  if (!head) {
    return null
  }
  const dummyHead = new ListNode(0, head)
  let [prev, fast, slow] = [dummyHead, head, head]
  while (fast && fast.next) {
    prev = slow
    slow = slow.next
    fast = fast.next.next
  }
  prev.next = null
  return new TreeNode(slow.val, sortedListToBST(dummyHead.next), sortedListToBST(slow.next))
}