109. Convert Sorted List to Binary Search Tree

题干简述：

给你一个单链表 ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡:二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路

本题实质是 108. Convert Sorted Array to Binary Search Tree 的变种。不同的地方在于， 108 给我们的是一个有序的数组，而这里给我们的是一个单链表。回顾一下单链表的定义，单链表每个节点由两个部分组成，该节点自身的 val 与指向该节点下一节点的指针。

解题思路还是一样，可以参考我的这篇题解 “有序数组转化为 BST”，讲的比较详细，通过递归倒推中序遍历即可。取巧的方法，是将这个有序单链表转化为同样顺序的数组，然后直接调用 “有序数组转化为 BST” 的方法即可。更正统的解决方法，就是利用单链表的性质。我们一般如何获取一个单链表的长度或者取其中间的节点呢？一般都是通过双指针方式来实现。

我们通过两个节点来存放指针，一个名为 slow ，用于存放正常的一次一步移动的指针；另一个名为fast ，用于存放一次移动两步的指针。slow 和 fast 每次同时移动，这样，当 fast 移动到最后时，slow 必然在这个单链表的中间位置。这样，结合我们对 No.108 的解题思路，就可以写出题解了。

题解

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(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;
};

Q.E.D.

Take it easy