LeetCode(109)Covert Sorted List to Binary Search Tree

テーマ
Gven a singly linked list where elemens are sorted in ascending order,convert it to a height balanced BST.
分析
順序チェーンテーブルを指定して、バランスのとれた二叉ルックアップツリーを構築します.
上の問題の本質と同じです.ただ違ったデータ構造を採用しています.この問題はチェーンブロックの節点を正確に求めて、ルートノードの位置を計算して、右側のサブリンクを正しく分割することにあります.
注意:ポインタ処理は、空のポインタ参照が現れないようにしてください.
ACコード

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == NULL)
            return NULL;

        int size = 0;
        ListNode *p = head;
        while (p)
        {
            ++size;
            p = p->next;
        }

        ListNode *l = head, *r = NULL;

        //      ，          
        ListNode *pre = head;
        p = head;

        int i = 0;
        while (p && i < size / 2)
        {
            pre = p;
            p = p->next;
            ++i;
        }

        //p       
        TreeNode *root = new TreeNode(p->val);


        //         
        r = p->next;
        //        
        if (pre->next == p)
            pre->next = NULL;
        else
            l = NULL;

        root->left = sortedListToBST(l);
        root->right = sortedListToBST(r);
        return root;
    }
};

GitHubテストプログラムのソースコード