[LeetCode] 109. Convert Sorted List to Binary Search Tree

Problem : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

Use fast-slow pointer to find mid node of the given linked list.

Then create BST recursively.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;

        ListNode mid = breakInMiddle(head);

        return new TreeNode(
            mid.val,
            sortedListToBST(head != mid ? head : null),
            sortedListToBST(mid.next));
    }

    ListNode breakInMiddle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }

        if (pre != null) pre.next = null;
        return slow;
    }
}