建设装修网站网络广告的概念

41 排序链表

• 递归 + 归并排序
• 找到链表中心点，从中心点将链表一分为二。奇数个节点找中心点，偶数个节点找中心左边的点作为中心点。
• 快慢指针找中心点，当快指针移动到该段链表的最后一个元素时，慢指针所指向的节点为中心点。
• 找到中心点后，中心点.next = null，将链表从中间断开。分别将前一半链表的头节点（head）和后一半链表的头节点（中心点.next）进行下一次划分。
• 注意：快慢指针初始化时，快指针比慢指针快一步，方便链表只有2个节点时划分链表。
• 合并有序链表：
  (1) 建立新节点作为新链表的哨兵节点。
  (2) left，right 分别指向两个链表的头部，比较两个指针处节点值的大小，从小到大插入到有序链表中，指针交替前进，直至其中一个链表为空。将剩余的链表直接插入到有序链表的尾部。
  (3) 返回哨兵节点.next。

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var sortList = function(head) {if(head == null || head.next == null){ // 1个节点或0个节点return head;}let slow = head, fast = head.next;while(fast != null && fast.next != null){ // 奇数个节点fast = null停止，偶数个节点fast.next = null停止slow = slow.next;fast = fast.next.next;}let tmp = slow.next;slow.next = null;let left = sortList(head);let right = sortList(tmp);let dummy = new ListNode();let res = dummy;while(left != null && right != null){if(left.val < right.val){dummy.next = left;left = left.next;}else{dummy.next = right;right = right.next;}dummy = dummy.next;} dummy.next = left? left: right;return res.next; 
};

42 合并k个升序链表

• 方法1：最小堆。将头节点放入堆中，弹出最小值node，此时将node.next放入堆中，一直取到堆为空为止，每次取出最小值时，都将最小值的下一个节点放入堆中。
• 方法2：分治。这里给出该方法的代码。
• 将链表数组lists一分为二，先合并前一半链表，再合并后一半链表，最后完成全部链表的合并。
• 中心点为mid，前一半链表的区域为[左，mid]，后一半链表的区域为[mid + 1，右]。

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/var merge = function(left, right){let dummy = new ListNode();let cur = dummy;while(left != null && right != null){if(left.val < right.val){cur.next = left;left = left.next;}else{cur.next = right;right = right.next;}cur = cur.next;}cur.next = left? left: right;return dummy.next;
}/*** @param {ListNode[]} lists* @return {ListNode}*/
var mergeKLists = function(lists) {function partition(i, j){if(i == j){ // 区域内只有1个值return lists[i];}if(i > j){ // 非法区域return null;}let mid = Math.floor((i + j) / 2);let left = partition(i, mid);let right = partition(mid + 1, j);return merge(left, right);}return partition(0, lists.length - 1)
};

43 LRU缓存

• 哈希表 + 双向链表
• put：
  ① key不存在：创建新节点，添加进哈希表，添加到链表头部。如果当前容量 > capacity，删除链表尾部节点，删除哈希表中对应的项。
  ② key存在：通过哈希表找到key所在的节点，改变value，移动到链表头部。
• get：
  ① key不存在：返回 -1。
  ② key存在：通过哈希表找到key所在的节点，移动到链表头部，返回value。
• 这里给出的代码直接使用哈希表实现各类操作。
• this.map.delete(key); this.map.set(key, value);：先删除，再将该节点添加到最后。
• this.map.keys().next().value;：哈希表中第一个键值。

/*** @param {number} capacity*/
var LRUCache = function(capacity) {this.capacity = capacity;this.map = new Map();
};/** * @param {number} key* @return {number}*/
LRUCache.prototype.get = function(key) {if(this.map.has(key)){let value = this.map.get(key);this.map.delete(key);this.map.set(key, value);return value;}else{return -1;}
};/** * @param {number} key * @param {number} value* @return {void}*/
LRUCache.prototype.put = function(key, value) {if(this.map.has(key)){let value = this.map.get(key);this.map.delete(key);}this.map.set(key, value);if(this.map.size > this.capacity){this.map.delete(this.map.keys().next().value);}
};/*** Your LRUCache object will be instantiated and called as such:* var obj = new LRUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/

44 二叉树的中序遍历

• 方法1：递归法。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var inorderTraversal = function(root) {var res = [];var traversal = function(root){if(root == null){return;}traversal(root.left);  // 左res.push(root.val);    // 根traversal(root.right); // 右}traversal(root);return res;
};

• 方法2：迭代法。
• 遍历顺序与处理顺序不同。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var inorderTraversal = function(root) {var res = []; // 存放结果var vis = []; // 模拟遍历队列，存放访问过的元素while(root != null || vis.length != 0){if(root != null){vis.push(root);root = root.left;   // 左}else{root = vis.pop();res.push(root.val); // 根root = root.right;  // 右}}return res;
};

45 二叉树的最大深度

• 深度：任意节点到根节点的距离，使用前序遍历。
• 高度：任意节点到叶子节点的距离，使用后序遍历。
• 根节点的高度就是二叉树的最大深度。
• 这里使用后序遍历，即通过求根节点高度得出二叉树的最大深度。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var maxDepth = function(root) {if(root == null){return 0;}var leftheight = maxDepth(root.left);var rightheight = maxDepth(root.right);var height = Math.max(leftheight, rightheight) + 1;return height;
};