思路和数组差不多,只是链表需要通过快慢指针找到中间节点:
- 根据题目示例,如果节点个数为偶数个,应该将中间偏右的那个作为根节点;
- 不需要断链,如果断链反而麻烦很多。
总结一下如何定位中间偏右(偶数个节点数)的节点以及如何定位中间偏左的节点:
- 中间偏右:循环条件为
!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; } };