思路和数组差不多,只是链表需要通过快慢指针找到中间节点:

  • 根据题目示例,如果节点个数为偶数个,应该将中间偏右的那个作为根节点;
  • 不需要断链,如果断链反而麻烦很多。

总结一下如何定位中间偏右(偶数个节点数)的节点以及如何定位中间偏左的节点:

  • 中间偏右:循环条件为!fast && !fast->next
  • 中间偏左:循环条件为!fast->next && !fast->next->next
  • (本题需要根据上面略微修改一下)

代码如下:

class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return TreeNode类
     */
    TreeNode* sortedListToBST(ListNode* head) {
        // write code here
        return preOrder(head, nullptr);
    }

    TreeNode* preOrder(ListNode* head, ListNode *end) {
        // 快慢指针找中点
        if (head == end) return nullptr;
        ListNode *fast = head, *slow = head;
        while (fast != end && fast->next != end) {
            fast = fast->next->next;
            slow = slow->next;
        }
        TreeNode *root = new TreeNode(slow->val);
        // 构建左右
        root->left = preOrder(head, slow);
        root->right = preOrder(slow->next, end);
        return root;
    }
};