algos

原题描述 二叉搜索树迭代器 思路 模拟法。 用O(n)空间的数组保存中序遍历的结果，使用指针start保存当前迭代器所处的下标。 class BSTIterator { public: vector<int> vals; int len = 0; int start = -1; void _build(TreeNode* root) { if (!root) return; if (root->left) _build(root->left); vals.push_back(root->val); ++len; if (root->right) _build(root->right); } BSTIterator(TreeNode* root) { _build(root); } int next() { return vals[++start]; } bool hasNext() { return start + 1 < len; } }; 运行结果 执行用时：28 ms, 击败 91.85% 的用户 内存消耗：23.6 MB，超过 45.59% 的用户

原题描述 旋转链表 思路 简单题，可使用模拟法。注意处理空链表、k >=链表长度len等边界情况 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* rotateRight(ListNode* head, int k) { ListNode* cur = head; if (cur == nullptr) return 0; int len = 0; while (cur) ++len, cur = cur->next; int first = (len - (k % len)) % len; if (first == 0) return head; cur = head; for (int i = 0; i < first - 1; ++i) { cur = cur->next; } ListNode* last = cur->next; cur->next = nullptr; ListNode* ans = last; while (last->next) last = last->next; last->next = head; return ans; } }; 运行结果 执行用时：8 ms, 击败82.17%的用户 内存消耗：11.4 MB，超过44.80%的用户