Convert linked list to bst@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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

» Solve this problem

下面两种方法，第一种更快。因为不用做循环什么的。

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode *sortedListToBST(ListNode *head) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int len =0;
	ListNode *p = head;
	while(p)
	{
	len++;
	p = p->next;
	}
	return BuildBST(head, 0, len-1);
	}
	TreeNode* BuildBST(ListNode*& list, int start, int end)
	{
	if (start > end) return NULL;
	int mid = start+(end-start)/2; //if use start + (end - start) >> 1, test case will break, strange!
	TreeNode *leftChild = BuildBST(list, start, mid-1);
	TreeNode *parent = new TreeNode(list->val);
	parent->left = leftChild;
	list = list->next;
	parent->right = BuildBST(list, mid+1, end);
	return parent;
	}
	};

view raw convert linked list to bst hosted with ❤ by GitHub

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode *sortedListToBST(ListNode *head) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int len =0;
	ListNode *p = head;
	while(p)
	{
	len++;
	p = p->next;
	}
	return BuildBST(head, 0, len-1);
	}
	TreeNode* BuildBST(ListNode *list, int start, int end)
	{
	if (start > end) return NULL;
	int mid = start+(end-start)/2;
	ListNode *p=list;
	for(int i=0; i<mid; i++) p=p->next;
	TreeNode *parent = new TreeNode(p->val);
	parent->left = BuildBST(list, start, mid-1);
	parent->right = BuildBST(list, mid+1, end);
	return parent;
	}
	};

view raw convert linked list to bst ii hosted with ❤ by GitHub