go on, go on!

61. Rotate List

Analysis

好像做过跟这个题类似的旋转数组的题，把给定的链表当成循环链表，然后移动位置就可以了。

Code

先用数组来处理，可能思路会简单一点。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return nullptr;
        vector<ListNode*> tmp, list;
        ListNode *p = head;
        while(p != nullptr) {
            tmp.push_back(p);
            p = p->next;
        }
        int size = tmp.size();
        k %= size;
        if(k == 0) return head;
        for(int i = size - k; i < size; i++) {
            list.push_back(tmp[i]);
        }
        for(int i = 0; i < size - k; i++) {
            list.push_back(tmp[i]);
        }
        for(int i = 0; i < size - 1; i++) {
            list[i]->next = list[i + 1];
        }
        list[size - 1]->next = nullptr;
        return list[0];
    }
};

脑子抽了，在数组的下标上迷糊了好久...还是原来做过的类似题啊，废了🙃。
改成只用一个数组的：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return nullptr;
        vector<ListNode*> list;
        ListNode *p = head;
        while(p != nullptr) {
            list.push_back(p);
            p = p->next;
        }
        int size = list.size();
        k %= size;
        if(k == 0) return head;
        for(int i = size - k; i < size - 1; i++) {
            list[i]->next = list[i + 1];
        }
        list[size - 1]->next = list[0];
        for(int i = 0; i < size - k - 1; i++) {
            list[i]->next = list[i + 1];
        }
        list[size - k - 1]->next = nullptr;
        return list[size - k];
    }
};

再改成纯指针的：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return nullptr;
        ListNode *p = head;
        int cnt = 0;
        while(p != nullptr) {
            cnt++;
            p = p->next;
        }
        k %= cnt;
        if(k == 0) return head;
        p = head;
        ListNode *pre;
        int tmp = cnt - k;
        while(tmp--) {
            pre = p;
            p = p->next;
        }
        pre->next = nullptr;
        pre = p;
        while(p->next != nullptr) p = p->next;
        p->next = head;
        return pre;
    }
};

好像pre也可以省下？额，好像不行。

173. Binary Search Tree Iterator

Analysis

读完一遍题目，其实没太明白题目的意思。尝试的写了一下，竟然通过了，仔细一看这个题 80% 的通过率啊~

Code

class BSTIterator {
    vector<int> seq;
    int pointer, count;
public:
    void inorder(TreeNode *root) {
        if(root == nullptr) return;
        inorder(root->left);
        seq.push_back(root->val);
        inorder(root->right);
    }
    BSTIterator(TreeNode* root) {
        inorder(root);
        pointer = 0;
        count = seq.size();
    }
    
    int next() {
        return seq[pointer++];
    }
    
    bool hasNext() {
        if(pointer < count) return true;
        else return false;
    }
};