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