LeetCode OJ——Convert Sorted List to Binary Search Tree

http://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

将一个按照元素升序排列的链表转换成BST。根据自身性质“元素升序排列”，再参考将升序排列的数组转换成BST的上一道题目，只需要将对数组的处理方式变成对链表的。还是得好好利用元素已经升序排列这个性质，不用那种纯粹的重新生成一个BST，按照左转、右转、先左转后右转、先右转后左转。

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

struct TreeNode {
    int val;
    TreeNode *left;
     TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    void fun(ListNode *begin ,int len,TreeNode *node)
    {
        if(len == 1)
        {
            node->val = begin->val;
            return;
        }
        int leftlen = len/2;
        int rightlen = len - len/2 -1;

        ListNode *midNode = begin;
        int tt = leftlen;
        while(tt--)
            midNode = midNode->next;
        node->val = midNode->val;

        if(leftlen)
        {
            TreeNode *nodeLeft = new TreeNode(0);
            node->left = nodeLeft;
            fun(begin,leftlen,nodeLeft);
        }
        if(rightlen)
        {            
            TreeNode *nodeRight = new TreeNode(0);
            node->right = nodeRight;
            fun(midNode->next,rightlen,nodeRight);
        }        
    }

    TreeNode *sortedListToBST(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(head == NULL)
            return NULL;
        
        TreeNode *root = new TreeNode(0);
        //length
        ListNode *temp= head;
        int len = 0;
        while(temp)
        {
            len++;
            temp = temp->next;
        }
        fun(head,len,root);

        return root;        
    }
};

int main()
{
    Solution *mySolution = new Solution();
     
    ListNode *head = new ListNode(1);
    ListNode *n1 = new ListNode(3);
    head->next = n1;
    ListNode *n2 = new ListNode(5);
    n1->next = n2;
    ListNode *n3 = new ListNode(7);
    n2->next = n3;
    ListNode *n4 = new ListNode(9);
    n3->next = n4;
    ListNode *n5 = new ListNode(11);
    n4->next = n5;
    mySolution->sortedArrayToBST(head);
    
    return 0;
}