/**
 * 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:
    
    ListNode *getMidNode(ListNode *head){
        if(head==NULL || head->next==NULL)return head;
        ListNode* prev=NULL;        //指向pstep1的前一个节点
        ListNode* pstep1=head;      //每次向前移动一步
        ListNode* pstep2=head->next;    //每次向前移动两步
        //对于偶数链表，结束条件是pstep2->next==NULL
        //对于计数链表，结束条件是pstep2==NULL
        
        while(pstep2!=NULL && pstep2->next!=NULL){
            prev=pstep1;
            pstep1=pstep1->next;
            pstep2=pstep2->next->next;
        }
        
        //找到链表中间节点的同时，把链表分裂为前后两个独立的链表
        if(prev)prev->next=NULL;
        
        return pstep1;
    }

    TreeNode *sortedListToBST(ListNode *head) {
       if(head==NULL)return NULL;
       
       ListNode*mid=getMidNode(head);
       //创建根节点
       TreeNode*root=(TreeNode*)malloc(sizeof(TreeNode));
       root->val=mid->val;
       //创建左子树
       TreeNode*left=NULL;
       if(mid!=head)
            left=sortedListToBST(head);
       //创建右子树
       TreeNode*right=sortedListToBST(mid->next);
       //构造二叉树
       root->left=left;
       root->right=right;
       
       return root;
       
    }
};