学步园

链表实现的话，快慢指针

class Solution {
public:
	TreeNode* createbst(ListNode *lhs, ListNode *rhs)
	{
		if(lhs == rhs)
		{
			TreeNode *t = new TreeNode(lhs->val);
			return t;
		}
		if(lhs->next == rhs)
		{
			TreeNode *t = new TreeNode(lhs->val);
			TreeNode *y = new TreeNode(rhs->val);
			t->right = y;
			return t;
		}
		ListNode *p = lhs, *q = lhs, *p_pre = p;
		while(q->next->next && q->next != rhs && q->next->next != rhs)
		{
			q = q->next->next;				//快指针
			p_pre = p;            	 
			p = p->next;					//慢指针 
		}
		if(q->next->next == rhs)
		{
			p_pre = p;
			p = p->next;
		}
				
		TreeNode *t = new TreeNode(p->val);
		t->left = createbst(lhs, p_pre);
		t->right = createbst(p->next, rhs);
		
		return t;
	}
	
    TreeNode *sortedListToBST(ListNode *head) 
	{
		if(!head)
			return NULL;
       	ListNode *p = head;
       	 
       	while(p->next)
       	{
    	  	p = p->next;
       	}
       		
		return createbst(head, p);
    }
};