题目 思路 最大深度 = max(左子树深度, 右子树深度) + 1 ...

题目 思路 对于任意节点 先翻转左子树 再翻转右子树 交换左右孩子节点 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; } }

题目 思路 如何高效地选择最小节点 1.1. 归并排序 1.2. 小顶堆 Java 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode node : lists) { if (node != null) { pq.offer(node); } } ListNode dummy = new ListNode(0), tail = dummy; while (!pq.isEmpty()) { ListNode min = pq.poll(); tail.next = min; tail = min; if (min.next != null) { pq.offer(min.next); } } tail.next = null; return dummy.next; } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return mergeRange(lists, 0, lists.length - 1); } private ListNode mergeRange(ListNode[] lists, int l, int r) { if (l == r) { return lists[l]; } int m = l + (r - l) / 2; ListNode left = mergeRange(lists, l, m); ListNode right = mergeRange(lists, m + 1, r); return mergeTwo(left, right); } private ListNode mergeTwo(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; return dummy.next; } }

两数相加 题目 思路 同时遍历两个链表 + 维护一个进位 carry。 ...

题目 思路 如果链表无环，fast 会先走到 null，循环结束。 ...

环形链表2 题目 思路 用快慢指针判断是否有环 从相遇点定位入环点 把指针放在回头点，另外一个指针放在相遇点，两者每次都走一步，第一次相遇的就是入环点。 从头到入环点的距离为 a，入环点到相遇点沿着环走的距离为 b。 ...

K 个一组翻转链表 题目 思路 每轮探测是否有 K 个节点 翻转 head, tail 把翻转后的凭借回去。 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k <= 1) { return head; } ListNode dummy = new ListNode(0, head); ListNode pre = dummy; while (true) { ListNode tail = pre; for (int i = 0; i < k; i ++) { tail = tail.next; if (tail == null) { return dummy.next; } } ListNode next = tail.next; ListNode groupHead = pre.next; reverse(groupHead, tail); pre.next = tail; groupHead.next = next; pre = groupHead; } } private void reverse(ListNode head, ListNode tail) { ListNode prev = null; ListNode cur = head; ListNode stop = tail.next; while(cur != stop) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } } }

题目 思路 每次循环交换一对。 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode a = prev.next; ListNode b = a.next; prev.next = b; a.next = b.next; b.next = a; prev = a; } return dummy.next; } }

题目 思路 等价于找到正数第 len - n 个节点的前一个节点。 ...

随机链表的复制 题目 思路 把复制节点插入到原链表中 每个旧节点紧跟着它的复制节点 复制 random 指针 拆分链表 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } Node cur = head; while (cur != null) { Node copy = new Node(cur.val); copy.next = cur.next; cur.next = copy; cur = copy.next; } cur = head; while (cur != null) { Node copy = cur.next; copy.random = (cur.random == null) ? null : cur.random.next; cur = copy.next; } Node dummy = new Node(0); Node copyCur = dummy; cur = head; while (cur != null) { Node copy = cur.next; Node nextOld = copy.next; copyCur.next = copy; copyCur = copy; cur.next = nextOld; cur = nextOld; } return dummy.next; } }