9.14 小米软开笔试
单选11+多选9+编程2
选择题有一些操作系统的不太了解，其他难度不大
编程题
1. 局部反转链表（lc原题，java核心代码模式）
public ListNode<Integer> reverseBetween(ListNode<Integer> head, int left, int right) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode p = dummyHead;
ListNode q = dummyHead.next;
for (int i = 0; i < left - 1; i++) {
p = p.next;
q = q.next;
}
for (int i = 0; i < right - left; i++) {
ListNode moved = q.next;
q.next = q.next.next;
moved.next = p.next;
p.next = moved;
}
return dummyHead.next;
} 2. 二叉搜索树转换为双向链表，空间O(1)，时间O(n)
private Stack<Node> stack = new Stack<>();
public Node Convert(Node pRootOfTree) {
dfs(pRootOfTree);
Node right = null;
Node result = null;
while (!stack.isEmpty()) {
Node node = stack.pop();
node.right = right;
right = node;
if (!stack.isEmpty()) {
node.left = stack.peek();
}else {
result = node;
node.left = null;
}
}
return result;
}
public void dfs(Node root) {
if (root == null) {
return;
}
dfs(root.left);
stack.push(root);
dfs(root.right);
} 