1. 对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
出处：
https://edu.csdn.net/practice/26912048
代码：
#define null INT_MIN #include <bits/stdc++.h> using namespace std; #include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode *insertionSortList(ListNode *head) { ListNode *dummy = new ListNode(0, head); ListNode *lastSorted = head; ListNode *curr = head ? head->next : nullptr; while (curr) { if (lastSorted->val <= curr->val) lastSorted = lastSorted->next; else { ListNode *prev = dummy; while (prev->next->val <= curr->val) prev = prev->next; lastSorted->next = curr->next; curr->next = prev->next; prev->next = curr; } curr = lastSorted ? lastSorted->next : nullptr; } return dummy->next; } }; ListNode* buildNodeList(vector<int> vec) { ListNode *head = new ListNode(0); ListNode *p = head; for (size_t i = 0; i < vec.size(); i++) { ListNode *node = new ListNode(vec[i]); p->next = node; p = p->next; } return head->next; } string NodeList2String(ListNode *head) { if (head==nullptr) return "[]"; ListNode *p = head; string res; while (p != nullptr) { res.append(to_string(p->val)); res.append("->"); p = p->next; } res.append("null"); return res; } int main() { Solution s; vector<int> nums = {4,2,1,3}; ListNode *head = buildNodeList(nums); cout << NodeList2String(head) << endl; cout << NodeList2String(s.insertionSortList(head)) << endl; nums = {-1,5,3,4,0}; head = buildNodeList(nums); cout << NodeList2String(head) << endl; cout << NodeList2String(s.insertionSortList(head)) << endl; return 0; }
输出：
4->2->1->3->null
1->2->3->4->null
-1->5->3->4->0->null
-1->0->3->4->5->null
2. 找出小于平均值的数
从键盘输入一个正整数存入变量n中，再输入n个整数，然后找出所有小于平均值的数，并按输入顺序输出。
以下程序实现了这一功能，请你补全空白处内容：
```c++ #include <stdio.h> int main() { int i, n, sum = 0, a[100]; float ave; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; } ave = sum * 1.0 / n; for (i = 0; i < n; i++) { __________________; } return 0; } ```
出处：
https://edu.csdn.net/practice/26912049
代码：
#include <stdio.h> int main() { int i, n, sum = 0, a[100]; float ave; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; } ave = sum * 1.0 / n; for (i = 0; i < n; i++) { if (a[i] < ave) printf("%d", a[i]); } return 0; }
输出：
略
3. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
出处：
https://edu.csdn.net/practice/26912050
代码：
#include <bits/stdc++.h> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: int maxDepth(TreeNode *root) { int depth = 0; if (root == NULL) { return 0; } else { depth = max(maxDepth(root->left), maxDepth(root->right)); return 1 + depth; } } };
输出：
略，重复题目，见： https://hannyang.blog.csdn.net/article/details/129762828#t1
