9.14小米笔试C++

编程题

ps：前面的选填记不到了

T1 链表反转

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

#include 
#include 
#include 
#include 
#include 

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;
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

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

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

#include 
#include 
#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25