/** * 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} */ /** * @param {ListNode} head * @return {TreeNode} */ var sortedListToBST = function(head) { if (!head) return head; var slow = head; var fast = head; var prev = null; while (fast && fast.next) { fast = fast.next.next; prev = slow; slow = slow.next; } var node = new TreeNode(slow.val); // if prev is null, it means, slow and fast did not move, it means this half is done. // otherwise, prev is the end of the first half (left sub tree). And set prev.next = null. if (!prev) { head = null; } else { prev.next = null; } node.left = sortedListToBST(head); node.right = sortedListToBST(slow.next); return node; };