Convert Sorted List to Balanced BST

Description

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Example
               2
1->2->3  =>   / \
             1   3

Link

Lintcode_ladder

Method

1. use fast/slow pointer to get middle, then create a node with slow->val, then using recursive method to get its left and right
2. x

Example

1. 1

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        if (!head) {
            return nullptr;
        }
        // find middle point
        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        // create father
        TreeNode* root = new TreeNode(slow->val);
        // divide the list into two
        if (prev) {
           prev->next = nullptr; 
        } else {
           head = nullptr;
        }
        // process children
        root->right = sortedListToBST(slow->next);
        root->left = sortedListToBST(head);
        return root;
    }
};

Similar problems

x

Tags

x