[recommend for beginners]clean C++ implementation with detailed explaination


  • 1

    I have the simliar idea. But I meet a problem that I used to use the dummy node to find the middle node.

    So I have implemented almost the same code except that I use the dummy node to find the middle node.

    So the only difference happens when the linked-list length is even. My implementation find the left middle

    pointer while you find the right pointer. So I will meet the corner case. So I am wondering any one can

    help me solve the corner cases with dummy pointer coding style.

    Thank you very much !

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(!head)   return NULL;
            if(!head->next)  return new TreeNode(head->val);
            
            ListNode *dummy = new ListNode(-1);
            dummy->next=head;
            //find the middle pointer
            /***    what should I DO to use the dummy node     ***/
            //ListNode *slow=dummy, *fast=dummy;
            while(fast && fast->next){
                slow=slow->next;
                fast=fast->next->next;
            }
            
            //set the pointer previous to the middle pointer point to NULL
            //ListNode *temp=dummy;
            /***    what should I DO to use the dummy node     ***/
            while(temp->next!=slow){
                 temp=temp->next;   
            }
            temp->next=NULL;
            
            //revursively build the BST
            ListNode *left=head, *right=slow->next;
            TreeNode *root = new TreeNode(slow->val);
            root->left=sortedListToBST(left);
            root->right=sortedListToBST(right);
            return root;
        }
    };

  • 0
    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(!head)   return NULL;
            if(!head->next)  return new TreeNode(head->val);
            ListNode *mid, *right;
            mid = help(head);
            right = mid->next->next;
            TreeNode *root = new TreeNode(mid->next->val);
            mid->next = NULL;
            root->left = sortedListToBST(head);
            root->right = sortedListToBST(right);
            return root;
        }
        /*** return the previous pointer before the middle pointer  ***/
        ListNode* help(ListNode* head){
            ListNode *slow, *fast;
            ListNode *dummy=new ListNode(-1);
            dummy->next=head;
            slow=head, fast=head;
            while(fast && fast->next){
                dummy=dummy->next;
                slow=slow->next;
                fast=fast->next->next;
            }
            return dummy;
        }
    };

Log in to reply
 

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