Daily LeetCode Challenge - 109. Convert Sorted List to Binary Search Tree

Problem From.

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

오늘문제는 주어진 linked list 에서 binary search tree 를 만들어내는 문제였다.

이 문제는 two pointer 를 사용하여 풀 수 있었는데, 하나씩 순차적으로 탐색하는 slow node 를 두고 그것보다 하나씩 더 빠르게 탐색하는 fast node 를 둔 뒤에, 각각의 node 결과를 느린 slow 노드는 tree 의 왼쪽에 빠른 fast 노드는 tree 의 오른쪽에 두는 식으로 문제를 풀었다.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun sortedListToBST(head: ListNode?): TreeNode? {
        
        if (head == null) return null
        if (head.next == null) return TreeNode(head.`val`)

        var prev: ListNode? = ListNode(-1)
        var slow: ListNode? = head
        var fast: ListNode? = head

        while (fast != null && fast.next != null) {
            fast = fast.next.next
            prev = slow
            slow = slow?.next
        }

        prev?.next = null
        
        val tree = TreeNode(slow!!.`val`)
        tree.left = sortedListToBST(head)
        tree.right = sortedListToBST(slow!!.next)
        
        return tree
    }
}