【LeetCodeゼロブラシから】Convert Sorted List to Binary Search Tree

タイトル:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
回答:
秩序化されたシーケンスをバランスツリーに変換するには、再帰が重要です.すなわち,中点はルートノードとし,小部分は左サブツリーとして再帰し,大部分は右サブツリーとして再帰する.
ここの単一チェーンテーブルは「中点を探す」ことに難題をもたらし、スナップポインタのテクニックを使用することができます.速いポインタは1回2歩、遅いポインタは1歩、速いポインタは終点に着いて、遅いポインタは中点です.
注意:シングルチェーンテーブルの終点(終点が取れない)はNULLです.

/**
 * 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* sortedRangeToBST(ListNode* start, ListNode* end) {
        if(start == end)    return NULL;
        
        ListNode* p = start;
        ListNode* q = start;
        
        while(q != end && q->next != end) {
            p = p->next;
            q = q->next->next;
        }
        
        TreeNode* mid = new TreeNode(p->val);
        mid->left   = sortedRangeToBST(start, p);
        mid->right  = sortedRangeToBST(p->next, end);
        return mid;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        return sortedRangeToBST(head, NULL);
    }
};