Day12--HOT100--23. 合并 K 个升序链表，146. LRU 缓存，94. 二叉树的中序遍历

方法：暴力

思路：

遍历lists的头节点，每次取最小值，移除头结点，直到所有链表都被移除完。

使用nullCount == n控制循环退出。

时间复杂度很高，多少个节点就遍历多少次。

class Solution {public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;// 因为新链表的头不一定，所以需要一个哨兵指向头的前一位ListNode dummy = new ListNode(-1);// 新链表的指针ListNode p = dummy;while (true) {// 使用nullCount == n控制循环退出int nullCount = 0;// 找到链表头是最小值的那个链表int index = 0;int minVal = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {// 记录已经是null的链表if (lists[i] == null) {nullCount++;} else if (lists[i].val < minVal) {minVal = lists[i].val;index = i;}}// 全部链表为空，退出if (nullCount == n) {break;}// 拼接在新链表的尾巴上，p指向下一位p.next = lists[index];p = p.next;// 该链表的头已经被拼走了，指针指向下一位。lists[index] = lists[index].next;}return dummy.next;}
}

方法：小顶堆

思路：

使用小顶堆，每个链表把自己的最小节点放到堆里面去。这样不用每次都遍历一遍。

1. 准备工作：new一个小顶堆。先遍历第一次，把所有非空链表的头节点入堆
2. 定义哨兵节点，作为合并后链表头节点的前一个节点——为了找回新的头
3. 循环直到堆为空
   1. 因为是小顶堆，每次取都是最小值的节点node
   2. 把 node 添加到新链表的末尾
   3. cur指针后移，准备合并下一个节点
   4. 如果该链表还有元素，把该链表的下一个节点入堆。

class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));// 准备工作：先遍历第一次，把所有非空链表的头节点入堆for (ListNode head : lists) {if (head != null) {pq.offer(head);}}// 哨兵节点，作为合并后链表头节点的前一个节点——为了找回新的头ListNode dummy = new ListNode();ListNode cur = dummy;// 循环直到堆为空while (!pq.isEmpty()) {// 因为是小顶堆，每次取都是最小值的节点ListNode node = pq.poll();// 把 node 添加到新链表的末尾cur.next = node;// 指针后移，准备合并下一个节点cur = cur.next;// 如果该链表还有元素，把该链表的下一个节点入堆。if (node.next != null) {pq.offer(node.next);}}return dummy.next;}
}

方法：递归

思路：

分治。两两合并后返回。（来自@灵茶山艾府)

class Solution {public ListNode mergeKLists(ListNode[] lists) {return mergeKLists(lists, 0, lists.length);}// 合并从 lists[i] 到 lists[j-1] 的链表// 这里的ij是左闭右开的private ListNode mergeKLists(ListNode[] lists, int l, int r) {int len = r - l;if (len == 0) {return null; // 注意输入的 lists 可能是空的}if (len == 1) {return lists[l]; // 无需合并，直接返回}ListNode left = mergeKLists(lists, l, l + len / 2); // 合并左半部分ListNode right = mergeKLists(lists, l + len / 2, r); // 合并右半部分return mergeTwoLists(left, right); // 最后把左半和右半合并}// 21. 合并两个有序链表private ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑ListNode cur = dummy; // cur 指向新链表的末尾while (list1 != null && list2 != null) {if (list1.val < list2.val) {cur.next = list1; // 把 list1 加到新链表中list1 = list1.next;} else { // 注：相等的情况加哪个节点都是可以的cur.next = list2; // 把 list2 加到新链表中list2 = list2.next;}cur = cur.next;}cur.next = list1 != null ? list1 : list2; // 拼接剩余链表return dummy.next;}
}

思路：

手写LinkedHashMap实现。

使用普通HashMap存储<key,Node>映射关系，手动实现双向链表记录访问顺序。

• 重点在于维护节点的访问顺序：（也就是维护双向链表）
  • get：先删除节点，再移动到链表的尾端（表示最新访问的key），返回节点。
  • put
    • 如果是新节点，直接put在尾端。
      • 当put达到容量capacity时，删除链表头结点（表示最旧访问的key）
    • 如果是旧节点，map更新value，链表删除节点，再在链表尾端put新节点。

public class LRUCache {class Node {int key;int value;Node prev;Node next;public Node() {}public Node(int key, int value) {this.key = key;this.value = value;}}private Map<Integer, Node> cache;private int size;private int capacity;private Node head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;cache = new HashMap<Integer, Node>(capacity);// 伪头部（最久未访问端）和伪尾部（最近访问端），简化边界操作head = new Node();tail = new Node();head.next = tail;tail.prev = head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}//  key存在：将该节点移到尾部moveToTail(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);//  key存在：更新value并移到尾部if (node != null) {node.value = value;moveToTail(node);} else {//  key不存在：创建新节点Node newNode = new Node(key, value);cache.put(key, newNode);// 添加到尾部addToTail(newNode);size++;// 容量满时：删除头部（最久未访问端）节点if (size > capacity) {Node removedNode = removeHead();cache.remove(removedNode.key);size--;}}}// 新节点添加到尾部private void addToTail(Node node) {node.prev = tail.prev;node.next = tail;tail.prev.next = node;tail.prev = node;}// 从链表中移除指定节点private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}// 将指定节点移到尾部private void moveToTail(Node node) {// 先从原位置移除节点removeNode(node);// 再添加到尾部addToTail(node);}// 删除头部节点（伪头部的下一个节点）private Node removeHead() {Node removedNode = head.next;removeNode(removedNode);return removedNode;}
}

思路：

直接继承LinkedHashMap实现。

不过面试一般不会这么考察，没什么需要你写的代码了。除了可以展示你对库函数的熟练程度。

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {// 这里的true，表示开启accessOrder，链表会维护访问顺序// 开启之后，最新访问的值，会移动到最尾端。super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}// 当什么情况下，删除最旧访问节点。默认是返回false，要重写。@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}

思路：

调用LinkedHashMap实现，写核心逻辑。

1. get的时候，要先remove原来的，再put进去，这样才会在链表的尾部，才会被视作最新访问的元素
2. put的时候
   • 情况一：如果原来有这个key，remove掉原来的，put新值，此时key会去到链表尾部。
   • 情况二：如果原来没有这个key。put进去。如果容量超了，把最旧的值remove掉（使用迭代器拿到第一个key）

class LRUCache {private final int capacity;private final Map<Integer, Integer> cache = new LinkedHashMap<>();public LRUCache(int capacity) {this.capacity = capacity;}// 要先remove原来的，再put进去，这样才会在链表的尾部，才会被视作最新访问的元素public int get(int key) {Integer value = cache.get(key);if (value != null) {cache.remove(key);cache.put(key, value);return value;}return -1;}public void put(int key, int value) {// 情况一：如果原来有这个key，remove掉原来的，put新值，此时key会去到链表尾部。if (cache.get(key) != null) {cache.remove(key);cache.put(key, value);return;}// 情况二：如果原来没有这个key// put进去cache.put(key, value);// 如果容量超了，把最旧的值remove掉if (cache.size() > capacity) {// 使用迭代器拿到第一个keyInteger eldestKey = cache.keySet().iterator().next();cache.remove(eldestKey);}}
}

方法：迭代

思路：

左中右遍历。

class Solution {private List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {backtrack(root);return res;}private void backtrack(TreeNode node) {if (node == null) {return;}backtrack(node.left);res.add(node.val);backtrack(node.right);}
}

方法：迭代

思路：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.push(cur);cur = cur.left;} else {cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}
}