Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
基本上是自己想的，只有一个地方参考了答案：就是如何记录链表中点前面那个点，也就是代码里的last这个ListNode应该怎么找到。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}
return helper(head);
}
private TreeNode helper(ListNode head){
if (head == null){
return null;
}
if (head.next == null){
return new TreeNode(head.val);
}
if (head.next.next == null){
TreeNode root = new TreeNode(head.next.val);
root.left = new TreeNode(head.val);
return root;
}
ListNode fast, slow, last;
fast = head;
slow = head;
last = head;
while (fast.next != null && fast.next.next != null){
last = slow;
fast = fast.next.next;
slow = slow.next;
}
fast = slow.next;
last.next = null;
TreeNode root = new TreeNode(slow.val);
root.left = helper(head);
root.right = helper(fast);
return root;
}
}
