In-place conversion of Sorted DLL to Balanced BST

Given a Doubly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion)

ListNode{
    ListNode pre, next;
    int val;
    ListNode(int val){
        this.val=val;
    }
}

Solution One

O(nlgn) time complexity, O(lgn) space complexity

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

@Method
public static ListNode convert(ListNode head){
    if(head==null || head.next==null) return head;
    ListNode slow=head, fast=head;
    while(fast!=null&&fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    if(slow.pre!=null) slow.pre.next=null;
    if(slow.next!=null) slow.next.pre=null;
    slow.pre=convert(head);
    slow.next=convert(slow.next);
    return slow;
}

Solution two

o(n) time complexity, O(lgn) space complexity

1. We first count the number of nodes in the given Linked List. Let the count be n. 
2. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. 
3. After left subtree is constructed, we assign middle node to root and link the left subtree with root. 
4. Finally, we recursively construct the right subtree and link it with root.
5. While constructing the BST, we also keep moving the list head pointer to next 
so that we have the appropriate pointer in each recursive call.

@Method
public static ListNode convert(ListNode head){
    if(head==null || head.next==null) return head;
    int n=0;
    ListNode ptr=head;
    while(ptr!=null){
        n++;
        ptr=ptr.next;
    }
    return build(head, n);
}

public ListNode build(ListNode head, int n){
    if(n<=0) return null;
    ListNode left=build(head, n/2);
    ListNode root=head;
    root.pre=left;
    head=head.next;
    root.next=build(head, n-n/2-1);
    return root;
}