

0141-0150

141. Linked List Cycle $\star$

class Solution {
 public:
  bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast) return true;
    }

    return false;
  }
};

142. Linked List Cycle II $\star\star$

class Solution {
 public:
  ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast) {
        slow = head;
        while (slow != fast) {
          slow = slow->next;
          fast = fast->next;
        }
        return slow;
      }
    }

    return nullptr;
  }
};

143. Reorder List $\star\star$

class Solution {
 public:
  void reorderList(ListNode* head) {
    if (!head || !head->next) return;

    ListNode* prev = NULL;
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* l1 = head;

    while (fast && fast->next) {
      prev = slow;
      slow = slow->next;
      fast = fast->next->next;
    }
    prev->next = NULL;

    ListNode* l2 = reverse(slow);
    merge(l1, l2);
  }

 private:
  ListNode* reverse(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;

    while (curr) {
      auto next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

  void merge(ListNode* l1, ListNode* l2) {
    while (l2) {
      auto next = l1->next;
      l1->next = l2;
      l1 = l2;
      l2 = next;
    }
  }
};

144. Binary Tree Preorder Traversal $\star\star$

class Solution {
 public:
  vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};

    vector<int> ans;

    stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.empty()) {
      TreeNode* node = stack.top();
      ans.push_back(node->val);
      stack.pop();
      if (node->right) stack.push(node->right);
      if (node->left) stack.push(node->left);
    }

    return ans;
  }
};

145. Binary Tree Postorder Traversal $\star\star\star$

class Solution {
 public:
  vector<int> postorderTraversal(TreeNode* root) {
    if (!root) return {};

    vector<int> ans;

    stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.empty()) {
      TreeNode* node = stack.top();
      ans.push_back(node->val);
      stack.pop();
      if (node->left) stack.push(node->left);
      if (node->right) stack.push(node->right);
    }

    reverse(ans.begin(), ans.end());

    return ans;
  }
};

146. LRU Cache $\star\star$

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    if (!map.count(key)) return -1;
    cache.splice(cache.begin(), cache, map[key]);
    return map[key]->second;
  }

  void put(int key, int value) {
    if (map.count(key)) {
      map[key]->second = value;
      cache.splice(cache.begin(), cache, map[key]);
      return;
    }

    if (cache.size() == capacity) {
      pair<int, int>& node = cache.back();
      map.erase(node.first);
      cache.pop_back();
    }

    cache.emplace_front(key, value);
    map[key] = cache.begin();
  }

 private:
  int capacity;
  list<pair<int, int>> cache;
  unordered_map<int, list<pair<int, int>>::iterator> map;
};

147. Insertion Sort List $\star\star$

class Solution {
 public:
  ListNode* insertionSortList(ListNode* head) {
    ListNode dummy(0);
    ListNode* curr = head;

    while (curr) {
      auto prev = &dummy;
      while (prev->next && prev->next->val < curr->val) prev = prev->next;
      auto next = curr->next;
      curr->next = prev->next;
      prev->next = curr;
      curr = next;
    }

    return dummy.next;
  }
};

148. Sort List $\star\star$

class Solution {
 public:
  ListNode* sortList(ListNode* head) {
    int length = 0;
    for (auto curr = head; curr; curr = curr->next) ++length;

    ListNode dummy(0);
    dummy.next = head;

    for (int k = 1; k < length; k <<= 1) {
      ListNode* curr = dummy.next;
      ListNode* tail = &dummy;
      while (curr) {
        ListNode* l = curr;
        ListNode* r = split(l, k);
        curr = split(r, k);
        vector<ListNode*> merged = merge(l, r);
        tail->next = merged[0];
        tail = merged[1];
      }
    }

    return dummy.next;
  }

 private:
  ListNode* split(ListNode* head, int k) {
    while (--k && head) head = head->next;
    ListNode* rest = head ? head->next : NULL;
    if (head) head->next = NULL;
    return rest;
  }

  vector<ListNode*> merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
      if (l1->val > l2->val) swap(l1, l2);
      tail->next = l1;
      l1 = l1->next;
      tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    while (tail->next) tail = tail->next;

    return {dummy.next, tail};
  }
};

149. Max Points on a Line $\star\star\star$

class Solution {
 public:
  int maxPoints(vector<vector<int>>& points) {
    int ans = 0;

    for (int i = 0; i < points.size(); ++i) {
      map<pair<int, int>, int> map;
      vector<int> p1 = points[i];
      int samePoints = 1;
      int maxPoints = 0;
      for (int j = i + 1; j < points.size(); ++j) {
        vector<int> p2 = points[j];
        if (p1[0] == p2[0] && p1[1] == p2[1])
          ++samePoints;
        else
          maxPoints = max(maxPoints, ++map[getSlope(p1, p2)]);
      }
      ans = max(ans, samePoints + maxPoints);
    }

    return ans;
  }

 private:
  pair<int, int> getSlope(vector<int>& p1, vector<int>& p2) {
    int dx = p2[0] - p1[0];
    int dy = p2[1] - p1[1];

    if (dy == 0) return {p1[1], 0};
    if (dx == 0) return {0, p1[0]};

    int d = gcd(dx, dy);

    return {dy / d, dx / d};
  }

  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
};

150. Evaluate Reverse Polish Notation $\star\star$

class Solution {
 public:
  int evalRPN(vector<string>& tokens) {
    stack<int> stack;
    int a;
    int b;

    for (string& token : tokens) {
      if (token == "+") {
        helper(stack, a, b);
        stack.push(a + b);
      } else if (token == "-") {
        helper(stack, a, b);
        stack.push(a - b);
      } else if (token == "*") {
        helper(stack, a, b);
        stack.push(a * b);
      } else if (token == "/") {
        helper(stack, a, b);
        stack.push(a / b);
      } else {
        stack.push(stoi(token));
      }
    }

    return stack.top();
  }

 private:
  void helper(stack<int>& stack, int& a, int& b) {
    b = stack.top();
    stack.pop();
    a = stack.top();
    stack.pop();
  }
};