思路

使用快慢指针，每次将中间节点当做根节点，一部分是左节点，一部分是右节点，然后递归

代码

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {TreeNode}
  4.  */
  5. var sortedListToBST = function(head) {
  6.     // 判断边界条件
  7.     if (!head) return null;
  8.     if (!head.next) return new TreeNode(head.val);
  9.     let pre = head, cur = pre.next, next = cur.next;
  10.     while(next && next.next) {
  11.         pre = pre.next;
  12.         cur = pre.next;
  13.         next = next.next.next;
  14.     }
  15.     // 断开链表
  16.     pre.next = null;
  17.     // 当前根节点
  18.     const root = new TreeNode(cur.val);
  19.     root.left = sortedListToBST(head);
  20.     root.right = sortedListToBST(cur.next);
  21.     return root;
  22. };

复杂度分析

时间复杂度 day9.[链表].109. 有序链表转换二叉搜索树 - 图1#card=math&code=O%28nlogN%29)

空间复杂度 day9.[链表].109. 有序链表转换二叉搜索树 - 图2#card=math&code=O%28N%29)