C++ solution using slow/fast pointers to find the middle of the list


  • 0
    G
    class Solution {
    public:
        
        pair<ListNode *, ListNode *> getMiddle(ListNode *head){
            ListNode *slow = head;
            ListNode *prev = slow;
            ListNode *fast = head != nullptr && head->next != nullptr ? head->next->next : nullptr;
            
            while(fast != nullptr){
                prev = slow;
                slow = slow->next;
                fast = fast->next != nullptr ? fast->next->next : nullptr;
            }
            
            return make_pair(prev,slow);
        }
        
        TreeNode* sortedListToBST(ListNode* head) {
            
           if(head == nullptr){
               return nullptr;
           }
            
           pair<ListNode *,ListNode *> p = getMiddle(head);
           
           TreeNode *m = new TreeNode(p.second->val);
            
           if(p.first != p.second){
               p.first->next = nullptr;
               m->left = sortedListToBST(head);
           }
            
           m->right = sortedListToBST(p.second->next);
           return m;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.