# \[109]\[中等]\[DFS]\[双指针] 有序链表转换二叉搜索树

## 题目描述

[109. 有序链表转换二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/)

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

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

示例:

```
给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
```

## 解题思路

### 转成数组

一个直接的思路就是先将整个列表过一遍, 将每个节点的值取出来组成一个**递增**的数组, 这样问题就转换成了 [108. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/). 实际上这种方法的效率也是比较高的. 解法如下:

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        nums = []
        current = head
        while current is not None:
            nums.append(current.val)
            current = current.next

        n = len(nums)

        def get_root(l, r):
            if l > r:
                return None

            mid = (l + r) // 2
            root = TreeNode(nums[mid])
            root.left = get_root(l, mid - 1)
            root.right = get_root(mid + 1, r)
            return root
        return get_root(0, n - 1)
```

### 快慢指针(双指针)

如果不转成数组, 只是用链表的方法, 我们仍然要找到中间节点. 常常使用**双指针**, 一快一慢, **快慢指针**配合找到中间节点. 分别定义为`slow_ptr`和`fast_ptr`, `slow_ptr`每次移动一个结点, `fast_ptr`每次移动两个结点, 这样当`fast_ptr`移动到链表的截尾时, `slow_ptr`正好访问到中间节点, 无论链表的长度奇偶.

仍然使用**递归**方法, 找到中间节点后, 将中间节点的前后断开, 然后前后子链再递归地使用同样的方法找到中间节点. 为了找到中间节点, 即`slow_ptr`, 再使用一个指针`prev_ptr`, 记录`slow_ptr`前一个元素.

具体内容参考:

[有序链表转换二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/you-xu-lian-biao-zhuan-huan-er-cha-sou-suo-shu-by-/)

```python
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        def get_root(pointer):
            if pointer is None:
                return None
            if pointer.next is None:
                return TreeNode(pointer.val)

            fast, slow, pre = pointer, pointer, None
            while fast is not None and fast.next is not None:
                fast = fast.next.next
                pre = slow
                slow = slow.next

            root = TreeNode(slow.val)
            pre.next = None  # 切断左子链与后面的连接, 进入递归
            root.left = get_root(pointer)
            root.right = get_root(slow.next)
            return root
        return get_root(head)
```

## 相关题目

* 数组版: [108. 将有序数组转换为二叉搜索树](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/)