【Day 10】160. 相交链表.md

思路

没得思路，看的官方题解😢。

代码

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode mid = getMedian(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left, mid);
        root.right = buildTree(mid.next, right);
        return root;
    }

    public ListNode getMedian(ListNode left, ListNode right) {
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

}

复杂度分析

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(logn)，平衡二叉树的高度为O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。