9.14小米笔试C++

编程题

ps：前面的选填记不到了

T1 链表反转

没啥好说的，就简单的链表反转一下，经典题目了

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <stack>

using namespace std;

template <class Type> class ListNode {
public:
    Type data;
    ListNode<Type> *next;
};

class Solution {
public:

    /* Write Code Here */
    ListNode < int > *reverseBetween(ListNode<int> *head, int left, int right) {
        ListNode<int> *p1,*p2;
        ListNode<int> *p3 = new ListNode<int>();
        p3->next = head;
        p1 = p2 = p3;
        int i = 1;
        while(i < left && p1)  {
            i++;
            p1 = p1->next;
        }
        ListNode<int> *p4 = p1;
        p1 = p1->next;
        i = 1;
        while(i <= right && p2)  {
            i++;
            p2 = p2->next;
        }
        stack<ListNode<int> *> St;
        while(p1 != p2) {
            St.push(p1);
            p1 = p1->next;
        }
        p4->next = p1;
        p2 = p2->next;
        p4 = p4->next;
        while(St.size()) {
            p4->next = St.top();
            St.pop();
            p4 = p4->next;
        }
        p4->next = p2;
        return head;
    }
};
int main() {
    ListNode < int > *res = NULL;

    int head_size = 0;
    cin >> head_size;

    ListNode<int> *head = NULL, *head_curr = NULL;
    int head_item;
    for(int head_i=0; head_i<head_size; head_i++) {
        cin >> head_item;

        ListNode<int> *head_temp = new ListNode<int>();
        head_temp->data = head_item;
        head_temp->next = NULL;
        if (head == NULL) {
            head = head_curr = head_temp;
        } else {
            head_curr->next = head_temp;
            head_curr = head_temp;
        }
    }

    int left;
    cin >> left;



    int right;
    cin >> right;



    Solution *s = new Solution();
    res = s->reverseBetween(head, left, right);
    while (res != NULL) {
        cout << res->data << " ";
        res = res->next;
    }
    cout << endl;

    return 0;

}

T2 二叉搜索树转为双向链表

这里有点小意外，因为这里题目没有提供输入输出（CPP），于是我直接输入后排序输出了，不过貌似也通过了

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

#define int long long

signed main()
{
    vector<int> Vec;
    int x;
    while(cin>>x)
        Vec.push_back(x);
    sort(Vec.begin(),Vec.end());
    int n = Vec.size();
    if(n == 0)  {
        printf("0");
        return 0;
    }
    for(int i = 0;i < n; ++i) cout<<Vec[i]<<" ";
    for(int i = n - 1;i >= 0; --i) cout<<Vec[i]<<" \n"[i==0];

    return 0;
}