Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

分析：将一个按升序排列的单链表转换成一个平衡二叉查找树，难点在于如何确定单链表的中间节点，因为单链表不像数组那样可以直接得到n/2的数值。可以用两个指针的方法来解决这个问题。我们定义两个指针one_step,two_step，two_step每次移动两步，one_step每次移动一步，这样当two_step移动到链表尾的时候，one_step正好到达链表中间的位置。只要确定了单链表的中间节点，我们再递归的将该节点左侧和右侧的链表转换成BST。时间复杂度是O(n)，空间复杂度O(1)。

代码如下：

1 class Solution { 2 public: 3     TreeNode *sortedListToBST(ListNode *head) { 4         if(!head) return NULL; 5         ListNode * two_step = head; 6         ListNode * one_step = head, * pre_onestep = NULL; 7         while(two_step->next && two_step->next->next){ 8             two_step = two_step->next->next; 9             pre_onestep = one_step;10             one_step = one_step->next;11         }12         TreeNode * root = new TreeNode(one_step->val);13         if(pre_onestep){14             pre_onestep->next = NULL;15             root->left = sortedListToBST(head);16         }17         if(one_step->next)18             root->right = sortedListToBST(one_step->next);19         return root;20     }21 };