题目

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

分析

给定有序链表，构造平衡的二叉查找树。

与上题本质相同，只不过采用了不同的数据结构，本题关键在于准确求取链表节点数，并计算根节点所在位置，正确划分左右子树的子链表。

注意：指针处理，避免出现空指针引用。

AC代码

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    TreeNode* sortedListToBST(ListNode* head) {

        if (head == NULL)

            return NULL;

        int size = 0;

        ListNode *p = head;

        while (p)

        {

            ++size;

            p = p->next;

        }

        ListNode *l = head, *r = NULL;

        //查找中间节点，用于构造二叉树根节点

        ListNode *pre = head;

        p = head;

        int i = 0;

        while (p && i < size / 2)

        {

            pre = p;

            p = p->next;

            ++i;

        }

        //p节点作为根节点

        TreeNode *root = new TreeNode(p->val);

        // 其余节点为右子树

        r = p->next;

        //之前节点为左子树

        if (pre->next == p)

            pre->next = NULL;

        else

            l = NULL;

        root->left = sortedListToBST(l);

        root->right = sortedListToBST(r);

        return root;

    }

};

GitHub测试程序源码