leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0109.cpp (1108B)

      1 class Solution {
      2     struct record {
      3         TreeNode *root;
      4         ListNode *low, *high;
      5         record(TreeNode *root, ListNode *low = nullptr, ListNode *high = nullptr)
      6             : root(root), low(low), high(high) {}
      7     };
      8     ListNode *get_mid(ListNode *list, ListNode *end) {
      9         ListNode *slow, *fast;
     10         slow = fast = list;
     11         while (fast != end && fast->next != end) {
     12             fast = fast->next->next;
     13             slow = slow->next;
     14         }
     15         return slow;
     16     }
     17 
     18   public:
     19     TreeNode *sortedListToBST(ListNode *head) {
     20         stack<record> st;
     21         TreeNode *tree = new TreeNode(INT_MIN), *t;
     22         st.push({tree, head, nullptr});
     23         while (!st.empty()) {
     24             record r = st.top();
     25             st.pop();
     26             while (r.low != r.high) {
     27                 ListNode *mid = get_mid(r.low, r.high);
     28                 (mid->val >= r.root->val ? r.root->right : r.root->left) = t = new TreeNode(mid->val);
     29                 st.push({r.root = t, mid->next, r.high});
     30                 r.high = mid;
     31             }
     32         }
     33         return tree->right;
     34     }
     35 };