阅文-2023-秋招笔试

编程题1-奇偶链表

对于一个链表，按照 先访问偶数下标的节点再访问奇数下标的节点 重新排列

思路是：奇偶两个指针交替移动并改变指针指向，最后将偶指针的下一个指向保存的第一个奇节点，并把奇指针的下一个指向置空

ListNode* oddEvenList(ListNode* head) {

	// 如果长度是0或者1，没有操作的必要
	if (!head || !head->next) return head;

	// 空间复杂度要求原地修改，时间复杂度要求一次遍历
	ListNode* EvenNode = head;
	ListNode* OddNode = head->next;
	ListNode* save = head->next;

	while (OddNode->next) {
		EvenNode->next = OddNode->next;
		EvenNode = OddNode->next;
		if (EvenNode->next) {
			OddNode->next = EvenNode->next;
			OddNode = EvenNode->next;
		}
		else break;
	}
	OddNode->next = nullptr;	
	EvenNode->next = save;
	return head;
}

编程题2-最左子节点

打印一颗二叉树的最左下角子节点

思路是：层序遍历，输出最后一层第一个节点

但是我忘记怎么按层打印二叉树了（怎么给序列分层）

二叉树的层序打印用到了双向队列，按层的关键是int curSize=que.size()

vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> res;

	if (!root) return res;

	deque<TreeNode*> que;
	que.push_back(root);

	while (!que.empty()) {
		int curSize = que.size();
		res.push_back(vector<int>());
		for (int i = 0; i < curSize; i++) {
			TreeNode* node = que.front();
			que.pop_front();
			res.back().push_back(node->val);
			if (node->left) que.push_back(node->left);
			if (node->right) que.push_back(node->right);
		}
	}
	return res;
}

层序遍历写出来这题就很好做了，只要return res.back().front();
天，我真蠢